Доказательство.

Предположим противное, то есть. пусть существует машина Тьюринга Т, решающая проблему самоприместимости в указанном выше смысле. Построим новую машину Т₀ , добавив новое состояние q ₀ * и объявив его заключительным, а также добавив новые команды для состояния q ₀ , которое было заключительным в Т:

q ₀ a ₁ → a ₁ С q ₀ (1)

q ₀ a ₂ → a ₂ С q ₀ (2)

… q ₀ a _n →a _n С q ₀ * (n)

Рассмотрим теперь работу машины T₀ .

Пусть M– произвольная машина. Если M– самоприменима, то начальная конфигурация q ₁ a _i перейдет с помощью команд машины T через конечное число шагов в конфигурацию q ₀ a ₁ , далее применяется команда (1), и машина T₀ никогда не остановится. Если M– несамоприменима, то начальная конфигурация q ₁ a _i перейдет с помощью команд машины T через конечное число шагов в конфигурацию q ₀ a _n , далее применяется команда (n), и машина T₀ остановится.

Таким образом, машина T₀ применима к кодам несамоприменимых машин Т и неприменима к кодам самоприменимых машин Т.

Теперь применим машину T₀ к начальной конфигурации q ₁ a _i . Сама машина T₀ является либо самоприменимой, либо несамоприменимой. Если T₀ самоприменима, то по доказанному она никогда не остановится, начав с q ₁ a _i , и потому она несамоприменима. Если T₀ несамоприменима, то по доказанному, она останавливается через конечное число шагов, начав с q ₁ a _j , и потому она самоприменима. Получили противоречие, следовательно проблема самоприменимости алгоритмически неразрешима, что и требовалось доказать.

Проблема остановки алгоритмически неразрешима, т. к. если бы она была разрешимой, то мы получили бы разрешимость проблемы самоприменимости.

5. Неразрешимости логики первого порядка

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

Вывод неразрешимости логики первого порядка из неразрешимости проблемы остановки

Вообще, говорят, что проблема распознавания какого-либо свойства разрешима, если существует допускающий механическое вычисление тест (вычислимая, или эффективная, процедура), который, будучи применен к произвольному объекту соответствующего типа, по прошествии некоторого времени правильно классифицирует этот объект с точки зрения наличия или отсутствия у него некоторого свойства. (Слова «по прошествии некоторого времени» означают здесь «после некоторого конечного числа шагов».) Позитивным тестом называется эффективная процедура, устанавливающая по прошествии некоторого времени все случаи наличия соответствующего свойства и только их. Негативный тест – это эффективная процедура, обнаруживающая все случаи отсутствия свойства и только их. Проблема распознавания произвольного свойства разрешима тогда и только тогда, когда для него существует и позитивный, и негативный тесты; дело в том, что всякий объект может или обладать рассматриваемым свойством, или нет, и потому, обладая обоими тестами, можно применить их оба к интересующему объекту, выполняя поочередно шаги одного и другого, и после некоторого их количества обнаружить, обладает он этим свойством или нет. (Верно и обратное: всякий тест, устанавливающий через некоторое конечное число шагов, обладает данный объект рассматриваемым свойством или нет, реализует и позитивный, и негативный тесты для этого свойства) Нас будут интересовать сейчас свойства общезначимости и выполнимости, а в роли объектов «соответствующего типа» выступают формулы языка логики первого порядка.

Докажем, что для этих тестов не существует дополнительных – позитивного для выполнимости и негативного для общезначимости – и потому в логике первого порядка проблемы распознавания как общезначимости, так и выполнимости неразрешимы.

Докажем неразрешимость логики первого порядка от противного: покажем, что если бы соответствующий тест существовал, то проблема остановки оказалась бы разрешимой. Мы убедились, что проблема остановки неразрешима.

Наше доказательство от противного будет строиться так: мы покажем, как, располагая программой машины Тьюринга, а также натуральным числом n , можно эффективно построить такие конечное множество предложений Д и еще одно предложение Н, что Д ├ Н тогда и только тогда, когда рассматриваемая машина, будучи запущенной в состоянии n (т.е. когда она начинает работу в состоянии q ₁ , считывая при этом самую левую единицу в сплошном массиве из n единиц на ленте с пустыми символами в остальных клетках), в конце концов останавливается. Таким образом, мы определяем некоторую интерпретацию машины Тьюринга I. Формула Н в интерпретации I говорит, что машина в конце концов остановится, а формула из множества Д описывают работу машины. Введем функцию следования ' (где i' = i + 1 для всякого i). Таким образом, если бы мы могли решить проблему распознавания общезначимости предложений, мы смогли бы эффективно решать, остановится в конце концов или нет данная машина Тьюринга, поскольку логическое следование Д ├ Н имеет место тогда и только тогда, когда общезначима импликация F₁ F₂ …F_k →H, где F_i Д (i = 1,2,… k).

Будем считать, что клетки ленты машины Тьюринга занумерованы так:

…

-3

-2

-1

0

1

2

3

…

Будем также предполагать, что время разбито на бесконечную последовательность моментов t, в каждый из которых машина выполняет точно одну свою операцию, и что машина начинает работу в момент времени 0, считывая при этом содержимое клетки 0. Моменты времени предполагаются неограниченно продолжаемыми как в будущее, так и в прошлое, равно как и лента бесконечно простирается и вправо, и влево. Мы считаем, что машина «включается» в момент 0 и «выключается» в первый момент (если таковой наступит), который следует за моментом ее остановки; мы считаем, далее, что во все отрицательные моменты времени и во все моменты, следующие за моментом остановки машины, она не находится ни в каком состоянии, не считывает никакую из имеющихся клеток и никакой символ (даже пустой) не встречается нигде на ее ленте.

Каждому состоянию q _i , в котором может пребывать машина, ставится в соответствие некоторый двуместный предикатный символ Q_i , подобным же образом каждому символу a _j , который машина может считывать либо записывать, ставится в соответствие двуместный предикатный символ A_j . Помимо символов Q_i и A_j в формулах из множества Д {Н} могут встречаться только следующие символы: имя 0, одноместный функциональный символ ' и двуместный предикатный символ <.

В предполагаемой интерпретации I предложений из множества Д {Н} предметной областью являются целые числа. Имени 0 интерпретация I приписывает значение нуль, а функциональному символу ' – функцию следования. Символы Q_i , A_j и < интерпретируются следующим образом:

I объявляет Q_i истинным на паре t, x в точности тогда, когда машина в момент времени t находится в состоянии q _i , считывая при этом клетку с номером х .

I объявляет a _j истинным на паре t, x в точности тогда, когда вмомент t в клетке с номером х находится символ a _j ;

I объявляет < истинным на паре х, у в точности тогда, когда х меньше чем у.

Выясним теперь, какие функции содержатся в множестве Д. (Будем использовать переменную t в тех случаях, когда имеется в виду время, и переменные х и у, когда речь идет о клетках на ленте.) Пусть a _i , …, a _n – список символов, считываемых и записываемых машиной. Для каждой строки программы вида q _i a _j →a _p Cq _k мы включаем в множество Д формулу

(1) "x "y "t ((t Q_i x t A_j x ) → (t ' Q_k x t A_p x (y ≠ x → (t A₀ y → t 'A₀ y … t A_n y → t 'A_n y ) )))

(«Если в момент времени t машина находится в состоянии q _i , считывая при этом символ a _j в клетке х , то в момент t + 1 машина перейдет в состояние q _k , считывая при этом клетку х , в которой появится символ A_p , а во всех клетках, отличных от х , в момент t + 1 останутся те же символы, что в момент t для всех t и х. »)

Также в множество Д для каждой строки программы вида q _i a _j →a _j П q _k мы включаем формулу

(2) "x "y "t ((t Q_i x t A_j x ) → (t ' Q_k x ' (t A₀ y → t 'A₀ y) … (t A_n y → t 'A_n y )))

(«Если в момент времени t машина находится в состоянии q _i , считывая при этом символ a _j в клетке х , то в момент t + 1 машина перейдет в состояние q _k , считывая при этом клетку х + 1, и во всех клетках в момент t + 1 останутся те же символы, что в момент t для всех t и х. »)

Аналогично для строк вида q _i a _j →a _j Л q _k включаем в Д