Из Википедии, свободной энциклопедии
Перейти к навигацииПерейти к поиску

В модели теории , экспоненциальная функция проблема Тарская спрашивает ли теория о действительных числах вместе с экспоненциальной функцией является разрешимой . Альфред Тарский ранее показал, что теория действительных чисел (без экспоненциальной функции) разрешима .

Проблема

Упорядоченное вещественное поле R представляет собой структуру на языке упорядоченных колец L или  = (+, ·, -, <, 0,1), с обычной интерпретацией, данной каждому символу. Тарский доказал, что теория вещественного поля Th ( R ) разрешима. То есть для любого L или -предложения φ существует эффективная процедура определения того,

Затем он спросил, будет ли это по-прежнему так, если добавить к языку унарную функцию exp, которая интерпретировалась как экспоненциальная функция на R , чтобы получить структуру R exp .

Условные и эквивалентные результаты

Задача может быть сведена к нахождению эффективной процедуры для определения является ли любое данным экспоненциальной многочлен в п переменных и с коэффициентами в Z имеет решение в R н . Macintyre & Wilkie (1995) показали, что из гипотезы Шануэля следует, что такая процедура существует, и, следовательно, дали условное решение проблемы Тарского. Гипотеза Шануэля имеет дело со всеми комплексными числами, поэтому можно было бы ожидать, что она будет более сильным результатом, чем разрешимость R exp , и действительно, Макинтайр и Уилки доказали, что для вывода разрешимости этой теории требуется только реальная версия гипотезы Шануэля.

Даже реальная версия гипотезы Шануэля не является необходимым условием разрешимости теории. В своей статье Макинтайр и Уилки показали, что эквивалентный результат разрешимости Th ( R exp ) - это то, что они назвали гипотезой слабого Шануэля. Эта гипотеза утверждает, что существует эффективная процедура, которая при n  ≥ 1 и экспоненциальных многочленах от n переменных с целыми коэффициентами f 1 , ..., f n , g дает целое число η  ≥ 1, которое зависит от n , f 1 , ..., f n ,g , и такое, что если α  ∈  R n - неособое решение системы

то либо g ( α ) = 0, либо | g ( α ) | >  η −1 .

Обходной путь

В последнее время делаются попытки обработать теорию действительных чисел с помощью таких функций, как экспоненциальная функция или синус , ослабив разрешимость до более слабого понятия квазиразрешимости. Теория квазиразрешима, если существует процедура, которая определяет выполнимость, но может выполняться бесконечно для входных данных, которые не являются надежными в определенном, четко определенном смысле. Такая процедура существует для систем n уравнений от n переменных ( Franek, Ratschan & Zgliczynski 2011 ).

Ссылки