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

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

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

(4) 0 Q_i 0 0 A₁ 0 0 A₁ 0' … 0 A₁ 0^(n-1) "y ((y ≠ 0 y ≠ 0' … y ≠ 0^{( n -1))} → 0 A₀ 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, если она в это время находится в состоянии q _i , считывая при этом символ a _j , причем в машинной ?