Разрешимость теории действительных чисел первого порядка - Decidability of first-order theories of the real numbers

Язык первого порядка действительные числа это набор всех правильно сформированных предложений логика первого порядка которые включают универсальный и экзистенциальные кванторы и логические комбинации равенств и неравенств выражений над действительными переменными. Соответствующий первый порядок теория - это набор предложений, которые действительно соответствуют действительным числам. Существует несколько различных таких теорий с разной выразительной силой в зависимости от примитивных операций, которые разрешено использовать в выражении. Фундаментальный вопрос при изучении этих теорий заключается в том, являются ли они разрешимый: то есть есть ли алгоритм который может принимать предложение в качестве ввода и давать в качестве вывода ответ «да» или «нет» на вопрос, истинно ли предложение в теории.

Теория настоящие закрытые поля это теория, в которой примитивными операциями являются умножение и сложение; это означает, что в этой теории можно определить только реальные числа. алгебраические числа. Как доказано Тарский, это разрешимо; видеть Теорема Тарского – Зайденберга. и Исключение квантора. Современные реализации процедур принятия решений для теории реальных замкнутых полей часто основаны на исключении квантора цилиндрическое алгебраическое разложение.

Проблема экспоненциальной функции Тарского касается распространения этой теории на другую примитивную операцию, экспоненциальная функция. Остается открытым вопрос, разрешима ли она, но если Гипотеза Шануэля то из этого следует разрешимость этой теории.[1][2] Напротив, расширение теории вещественных замкнутых полей с функция синуса неразрешима, поскольку это позволяет кодировать неразрешимую теорию целых чисел (см. Теорема Ричардсона ).

Тем не менее, можно справиться с неразрешимым случаем с помощью таких функций, как синус, используя алгоритмы, которые не обязательно завершаются всегда. В частности, можно разработать алгоритмы, которые требуются только для завершения для входных формул, которые крепкий, то есть формулы, выполнимость которых не меняется, если формулу слегка нарушить.[3] В качестве альтернативы также можно использовать чисто эвристические подходы.[4]

Рекомендации

  1. ^ Macintyre, A.J .; Уилки, А.Дж. (1995), «О разрешимости действительного экспоненциального поля», в Odifreddi, P.G. (ред.), Том 70-летия Крейзеля, CLSI
  2. ^ Kuhlmann, S. (2001) [1994], «Модельная теория действительной экспоненциальной функции», Энциклопедия математики, EMS Press
  3. ^ Ратшан, Стефан (2006). «Эффективное решение количественных ограничений неравенства над действительными числами». Транзакции ACM по вычислительной логике. 7 (4).
  4. ^ Акбарпур, Бехзад; Полсон, Лоуренс Чарльз (2010). «МетиТарский: автоматическое средство доказательства теорем для вещественнозначных специальных функций». Журнал автоматизированных рассуждений. 44.