Неразрешимость логики первого порядка (стр. 4 из 7)
| … | -3 | -2 | -1 | 0 | 1 | 2 | 3 | … |
Будем также предполагать, что время разбито на бесконечную последовательность моментов 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– список символов, считываемых и записываемых машиной. Для каждой строки программы вида qiaj →apCqkмы включаем в множество Д формулу
(1) "x "y "t ((t Qi x
t Ajx) → (t' Qkx t Ap x (y ≠ x → (t A0y → t'A0y … tAny → t'Any))))(«Если в момент времени t машина находится в состоянии qi, считывая при этом символ aj в клетке х, то в момент t + 1 машина перейдет в состояние qk, считывая при этом клетку х, в которой появится символ Ap, а во всех клетках, отличных от х, в момент t + 1 останутся те же символы, что в момент t для всех t и х.»)
Также в множество Д для каждой строки программы вида qiaj →aj П qkмы включаем формулу
(2) "x "y "t ((t Qi x
t Ajx) → (t' Qkx' (t A0y → t'A0y) … (tAny → t'Any)))(«Если в момент времени t машина находится в состоянии qi, считывая при этом символ aj в клетке х, то в момент t + 1 машина перейдет в состояние qk, считывая при этом клетку х + 1, и во всех клетках в момент t + 1 останутся те же символы, что в момент t для всех t и х.»)
Аналогично для строк вида qiaj →ajЛ qkвключаем в Д
(3) "x "y "t ((t Qix'
t Ajx') → (t' Qkx (t A0y → t'A0y) … (tAny → t'Any)))(«Если в момент времени 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 A0y)Здесь 0(n-1) обозначает результат применения n символов следования к символу 0.
Еще одна из формула множества Д утверждает, что всякое целое число является следующим точно за одним целым:
(5) "z$xz = 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 – различные натуральные числа, то "xx(p) ≠ x(q).
Таким образом, Д состоит из формул (1), (2), (3), соответствующих всем командам машины, и трема дополнительными (4), (5), (6). Что касается предложения Н, то заметим, что всякая машина останавливается в момент времени t, если она в это время находится в состоянии qi, считывая при этом символ aj, причем в машинной таблице нет команды, соответствующей комбинации qiaj. Таким образом, за предложение Н мы принимаем дизъюнкцию всех предложений вида
$t $x (t Qix
t Aix),для которых в машинной таблице нет команд, соответствующих комбинациям qiaj. Если же для всякой такой комбинации в таблице имеются команды, то машина никогда не остановится, и за Н в этом случае мы принимаем какую-либо формулу, ложную в интерпретации I, например 0 ≠ 0.
Мы показали, как по данной машине и входному значению nпостроить такие конечное множество предложений Д и отдельное предложение Н, что соотношение Д ├ Н имеет место тогда и только тогда, когда машина, получив n на входе, в конце концов, останавливается.
Рассмотрим факты, касающиеся отношения ├ в логике первого порядка. Все предложения из множества Д истинны в интерпретации I. Поэтому если Д ├ Н, то и Н истинно в I. Но Н истинно в I тогда и только тогда, когда машина, получив на входе n, в конце концов останавливается.
Введем теперь один специальный тип формул, называемых нами описаниями времени s. Так называется всякая формула, определяющая очевидным способом, в каком состоянии находится машина в момент s, какая клетка ею в это время считывается, а также в каких клетках ленты какие символы записаны, причем все это делается на языке множества формул Д
{Н}. Точнее говоря, всякое описание времени s есть формула вида(7) 0(s)Qi0(p)
0(s) 
… 0(s)Aj0(p) … 0(s) 
"y ((y 
… y 0(p) … y 
) → 0(s)A0y)