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

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

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

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

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

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

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

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

Выясним теперь, какие функции содержатся в множестве Д. (Будем использовать переменную t в тех случаях, когда имеется в виду время, и переменные х и у, когда речь идет о клетках на ленте.) Пусть ai, …, an – список символов, считываемых и записываемых машиной. Для каждой строки программы вида qi aj → ap Cqk мы включаем в множество Д формулу

(1) "x "y "t ((t Qi x t Aj x) → (t' Qk x t Ap x (y ≠ x → (t A0 y → t' A0 y … t An y → t' An y))))

(«Если в момент времени t машина находится в состоянии qi, считывая при этом символ aj в клетке х, то в момент t + 1 машина перейдет в состояние qk, считывая при этом клетку х, в которой появится символ Ap, а во всех клетках, отличных от х, в момент t + 1 останутся те же символы, что в момент t для всех t и х.»)

Также в множество Д для каждой строки программы вида qi aj → aj П qk мы включаем формулу

(2) "x "y "t ((t Qi x t Aj x) → (t' Qk x' (t A0 y → t' A0 y) … (t An y → t' An y)))

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

Аналогично для строк вида qi aj → aj Л qk включаем в Д

(3) "x "y "t ((t Qi x' t Aj x') → (t' Qk x (t A0 y → t' A0 y) … (t An y → t' An y)))

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

Одно из предложений множества Д утверждает, что в начальный момент машина находится в состоянии q1, считывая при этом самую левую единицу в сплошном массиве единиц на ленте с пустыми символами в остальных клетках:

(4) 0 Qi 0 0 A1 0 0 A1 0' … 0 A1 0(n-1) "y ((y ≠ 0 y ≠ 0' … y ≠ 0(n-1)) → 0 A0 y)

Здесь 0(n-1) обозначает результат применения n символов следования к символу 0.

Еще одна из формула множества Д утверждает, что всякое целое число является следующим точно за одним целым:

(5) "z $x z = x' "z "x "y (z = x' z = y' → x = y)

Введем в Д еще одну формулу

(6) "x "y "z (x < y y < z → x < z) "x "y (x' = y → x < y) "x "y (x < y → x ≠ y),

из которого следует, что если p и q – различные натуральные числа, то "x x(p) ≠ x(q).

Таким образом, Д состоит из формул (1), (2), (3), соответствующих всем командам машины, и трема дополнительными (4), (5), (6). Что касается предложения Н, то заметим, что всякая машина останавливается в момент времени t, если она в это время находится в состоянии qi, считывая при этом символ aj, причем в машинной таблице нет команды, соответствующей комбинации qi aj. Таким образом, за предложение Н мы принимаем дизъюнкцию всех предложений вида

 Скачать реферат