Неразрешимость логики первого порядка
(«Если в момент времени t машина находится в состоянии qi, считывая при этом символ aj в клетке х, то в момент t + 1 машина перейдет в состояние qk, считывая при этом клетку х + 1, и во всех клетках в момент t + 1 останутся те же символы, что в момент t для всех t и х.»)
Аналогично для строк вида qi aj → aj Л qk включаем в Д
"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, считывая при этом самую левую единицу в сплошном массиве единиц на ленте с пустыми символами в остальных клетках:
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.
Еще одна из формула множества Д утверждает, что всякое целое число является следующим точно за одним целым:
"z
$x
z = x'
"z
"x
"y
(z = x'
z = y'
→ x = y)
Введем в Д еще одну формулу
"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. Таким образом, за предложение Н мы принимаем дизъюнкцию всех предложений вида
$t
$x
(t Qi
x
t Ai
x),
для которых в машинной таблице нет команд, соответствующих комбинациям qiaj. Если же для всякой такой комбинации в таблице имеются команды, то машина никогда не остановится, и за Н в этом случае мы принимаем какую-либо формулу, ложную в интерпретации I, например 0 ≠ 0.
Мы показали, как по данной машине и входному значению n построить такие конечное множество предложений Д и отдельное предложение Н, что соотношение Д ├ Н имеет место тогда и только тогда, когда машина, получив n на входе, в конце концов, останавливается.
Рассмотрим факты, касающиеся отношения ├ в логике первого порядка. Все предложения из множества Д истинны в интерпретации I. Поэтому если Д ├ Н, то и Н истинно в I. Но Н истинно в I тогда и только тогда, когда машина, получив на входе n, в конце концов останавливается.
Введем
теперь один
специальный
тип формул,
называемых
нами описаниями
времени s. Так
называется
всякая формула,
определяющая
очевидным
способом, в
каком состоянии
находится
машина в момент
s, какая клетка
ею в это время
считывается,
а также в каких
клетках ленты
какие символы
записаны, причем
все это делается
на языке множества
формул Д
{Н}. Точнее говоря,
всякое описание
времени s есть
формула вида
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),
а это предложение является описанием времени s + 1.
Если имеется стрелка типа (в), то одна из формул множества Д есть
"x
"y
"t
((t
Qi
x'
t
Aj
x')
→ (t'
Qk
x
(t
A0
y
→ t'
A0
y)
…
(t
An
y
→ t'
An
y)))
Тогда существует такой символ aq, что из последней формулы, объединенной с (5), (6), (8), следует
0(s+1)Qi0(p-1)
0(s+1)
…
0(s+1)Aj
0(p-1)
…
0(s+1)
"y
((y
y
0(p-1)
…
y
)
→ 0(s+1)A0
y)
а это предложение является описанием времени s + 1.
Во всех трех случаях множество Д имеет следствием некоторое описание времени s + 1, и тем самым неразрешимость логики первого порядка доказана.
Доказательство неразрешимости логики первого порядка методом Геделя
Для
доказательства
неразрешимости
логики первого
порядка достаточно
продемонстрировать,
как по данной
машине Т с входным
значением n
(то есть когда
машина находится
на самой левой
единице в сплошной
последовательности
из n
единиц при
пустых символах
в остальных
клетках ленты)
построить такие
предложение
I
и конечное
множество
предложений
Г, что машина
Т при входном
значении
останавливается
тогда и только
тогда, когда
Г ├ I.
Не
существует
эффективной
процедуры,
позволяющей
решать, останавливается
ли произвольная
машина Тьюринга
Т при произвольном
входном значении
n
и по данной
машине Тьюринга
Т можно построить
примитивно
рекурсивную
функцию g,
обладающую
следующим
свойством:
какое бы n
мы не взяли, g
(n,
t)
= 0 в точности
тогда, когда
t
– номер шага,
более позднего,
чем тот, на котором
машина T
останавливается,
если ее запустить
при входном
значении n.
(по определению
функции g,
если шаг t
не таков, то g
(x,
t)
= <a,
b,
c>
=
для некоторых
a,
b,
c
и потому g
(x,
t)
> 0. Если же t
– такой шаг, то
g
(x,
t)
= 0.
Таким образом, если дана машина Т, то можно эффективно построить некоторую конечную последовательность q0, q1, …, qr примитивно рекурсивных функций, удовлетворяющую двум условиям: 1) каждая функция gi либо является базисной функцией, либо получается из некоторых предыдущих функций с помощью композиции или примитивной рекурсии и 2) для всякого n машина T, запущенная на входном значении n, в конце концов останавливается тогда и только тогда, когда gr(n, t) = 0 для некоторого t.
Построим теперь по данной T последовательность примитивно рекурсивных функций, удовлетворяющую условиям 1) и 2). Каждой функции gi поставим в соответствие свой функциональный символ gi с тем же числом аргументов, что и gi. Пусть g0 = '. Используя эти символы, выпишем для каждого gi одну или две очевидные формулы, определяющие функцию gi Например,
если gi = z, то "x gi(x) = 0
если gi = s, то "x gi(x) = x'
если
gi
=
,
то "x1
… "xm
… "xn
gi(x1,
…, xm,
…, xn)
= xm
Если gi получается из предшествующих ей функций gj и gk c помощью примитивной рекурсии, то "x gi(x, 0) =gj(x) и "x "y gi(x, y') =gk(x, y, gi(x, y))
Если
же gi
получается
из предшествующих
ей функций gо
и
путем композиции,
то "x
gi(x)
=gj
(для краткости
заменили здесь
x1,
x2,
…, xn
на x,
a
"x1,
"x2,
…, "xn
на "x)
Запишем
также формулы
"x
x
' ≠ 0 и
"x
"y
(x
' = y
' → x
= y).
Обозначим
теперь через
Г множество
всех этих формул,
а через I – формулу
.
Утверждение.
Машина T
при входном
значении
останавливается
тогда и только
тогда, когда
Г ├ I.
«Тогда».
Пусть Г ├ I. Обозначим
через
модель, областью
которой служит
множество
натуральных
чисел и которая
интерпретирует
символ 0 как 0,
а функциональные
символы gi
– как
.
Все предложения
из Г истинны
в
.
Поскольку Г
├ I, предложение
I
истинно также.
Следовательно,
для некоторого
справедливо
.
Согласно 2), T
останавливается
на
.
«Только
тогда». Предположим,
что Т останавливается
при входном
значении
.
Для доказательства
соотношения
Г ├ I предположим,
что
– произвольная
модель, в которой
все предложения
из Г истинны,
и