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

$t $x (t Qi x t Ai x),

для которых в машинной таблице нет команд, соответствующих комбинациям 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)

Мы требуем при этом, чтобы последовательность целых чисел p1,…, р,…, pv была возрастающей; р может совпадать с р1 или с рv Заметим, что формула (4) является описанием времени 0.

Предположим теперь, что машина, получив на входе число n, в конце концов останавливается. Тогда для некоторых s, i, p и j машина в момент s окажется в состоянии qi, считывая при этом клетку с номером р, содержащую символ aj, причем в программе машинной нет команды для комбинации qiaj.

Предположим, далее, что из множества формул Д следует некоторое описание G времени s. Поскольку I – модель для Д, формула G должно быть истинным в I. Поэтому G должно содержать в качестве конъюнктивных членов формулы 0(s)Qi0(p) и 0(s)Aj0(p) а потому из G должна следовать формула

$t $x (t Qi x t Ai x),

входящее одним из дизъюнктивных членов в H. Поэтому Н будет следовать из Д.

Остается лишь показать, что для всякого неотрицательного s, если только машина не останавливается до момента s, из Д следует некоторое описание времени s. Докажем это индукцией по s.

Основание индукции. Пусть s = 0. Множество Д содержит, а потому и влечет за собой предложение (4), являющееся описанием времени 0.

Шаг индукции. Предположим, что выделенное курсивом предложение верно (для s). Предположим, далее, что наша машина не остановилась до момента s + 1. Это значит, что она не остановилась ни до момента s, ни в самый момент s. Тогда из Д следует некоторое описание (8) времени s. Нужно доказать, что из Д следует и некоторое описание времени s+1.

Поскольку I – модель для Д, формула (8) истинна в I. Поэтому в момент s машина находится в состоянии qi, считывая при этом некоторую клетку (с номером р), в которой записан символ aj. Поскольку машина в момент s не остановилась, в ее программе должна присутствовать команда одного из видов

(a) qi aj → ak С qm

(б) qi aj → aj П qm

(в) qi aj → aj Л qm

Если имеется команда типа (а), то одна из формул множества Д есть

"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))))

Она вместе с (5), (6) и (8) влечет за собой формулу

0 (s+1) Qi0 (p) 0 (s+1) Aj10 (p1) … 0 (s+1) Aj0 (p) … 0 (s+1) Ajv0 (pv) "y ((y ≠ 0 (p1) … y ≠ 0 (p) … y ≠ 0 (pv)) → 0 (s+1) A0y),

являющуюся описанием времени s + 1.

Еcли имеется команда типа (б), то одна из формул множества Д есть

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

Из этого предложения, объединенного с (5), (6) и (8), следует, что для некоторого символа ,

0(s+1)Qi0(p+1) 0(s+1) … 0(s+1)Aj0(p+1) … 0(s+1) "y ((y ≠ … y ≠ 0(p+1) … y ≠ ) → 0(s+1)A0y),

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