Теорема Ричардсона - Richardsons theorem

В математике Теорема Ричардсона устанавливает предел степени, в которой алгоритм может решать равны ли определенные математические выражения. Он утверждает, что для некоторого довольно естественного класса выражений это неразрешимый есть ли конкретное выражение E удовлетворяет уравнению E = 0, и аналогично неразрешимо, будут ли функции, определенные выражениями E и F везде равны (на самом деле E = F если и только если E − F = 0). Это было доказано в 1968 году ученым-компьютерщиком Дэниелом Ричардсоном из Университет Бата.

В частности, класс выражений, для которых справедлива теорема, порождается рациональными числами, число π, номер пер. 2, переменная Икс, операции сложения, вычитания, умножения, сочинение, а грех, exp, и пресс функции.

Для некоторых классов выражений (сгенерированных другими примитивами, кроме теоремы Ричардсона) существуют алгоритмы, которые могут определить, равно ли выражение нулю.[1]

Формулировка теоремы

Теорема Ричардсона может быть сформулирована следующим образом:[2] Позволять E быть набором выражений, которые представляют ℝ → ℝ функции. Предположим, что E включает эти выражения:

  • Икс (представляющий функцию идентичности)
  • еИкс (представляющие экспоненциальные функции)
  • грех Икс (представляющий функцию греха)
  • все рациональные числа, ln 2 и π (представляющие постоянные функции, которые игнорируют их ввод и производят данное число на выходе)

Предполагать E также закрывается при выполнении нескольких стандартных операций. В частности, предположим, что если А и B находятся в E, то в E:

  • А + B (представляющий собой точечное сложение функций, которые А и B представлять)
  • А – B (представляет собой точечное вычитание)
  • AB (представляющий поточечное умножение)
  • A∘B (представляющий собой состав функций, представленных А и B)

Тогда следующие проблемы решения неразрешимы:

  • Решаем, является ли выражение А в E представляет функцию, которая везде неотрицательна
  • Если E включает также выражение |Икс| (представляет функцию абсолютного значения), решая, является ли выражение А в E представляет функцию, которая везде равна нулю
  • Если E включает выражение B представляющая функцию, чья первообразный не имеет представителя в E, решая, является ли выражение А в E представляет функцию, первообразная которой может быть представлена ​​в E. (Пример: имеет первообразную в элементарные функции если и только если а = 0.)

Расширения

После Десятая проблема Гильберта было решено в 1970 г., Б. Ф. Кавинесс заметил, что использование еИкс и ln 2 можно было удалить.[3]П.С.Ванг позже заметил, что при тех же предположениях, при которых вопрос о существовании Икс с А(Икс) <0 был неразрешим, вопрос о существовании Икс с А(Икс) = 0 также не растворилось.[4]

Миклош Лацкович устранена также необходимость в π и уменьшено использование композиции.[5] В частности, учитывая выражение А(Икс) в кольце, порожденном целыми числами, Иксгрех Иксп, и грех (Икс грехИксп), как вопрос о том, А(Икс)> 0 для некоторых Икс и будь А(Икс) = 0 для некоторых Икс неразрешимы.

Напротив, Теорема Тарского – Зайденберга. говорит, что теория первого порядка реального поля разрешима, поэтому полностью удалить синусоидальную функцию невозможно.

Смотрите также

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

  1. ^ Дэн Ричардсон и Джон Фитч, 1994 г. "Проблема тождества элементарных функций и констант ", Труды международного симпозиума по символическим и алгебраическим вычислениям, стр. 85–290.
  2. ^ Ричардсон, Дэниел (1968). «Некоторые неразрешимые задачи, связанные с элементарными функциями действительной переменной». Журнал символической логики. 33 (4): 514–520. JSTOR  2271358. Zbl  0175.27404.
  3. ^ Кавинесс, Б.Ф. (1970). «О канонических формах и упрощении». Журнал ACM. 17 (2): 385–396. Дои:10.1145/321574.321591.
  4. ^ Ван, П. С. (1974). «Неразрешимость существования нулей вещественных элементарных функций». Журнал Ассоциации вычислительной техники. 21 (4): 586–589. Дои:10.1145/321850.321856.
  5. ^ Лацкович, Миклош (2003). «Удаление π из некоторых неразрешимых проблем с элементарными функциями». Proc. Амер. Математика. Soc. 131 (7): 2235–2240. Дои:10.1090 / S0002-9939-02-06753-9.

дальнейшее чтение

внешняя ссылка