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

Проблема разрешимости
Существует ли алгоритм, позволяющий установить, выполнима данная формула U исчисления предикатов или нет?

ИСЧИСЛЕНИЕ
ПРЕДИКАТОВ
НЕРАЗРЕШИМО

Доказательство
Для произвольной машины Тьюринга M мы построим формулу U(M) и покажем, что если существует метод определения, выполнима ли U(M), то существует метод определения, остановится ли МТ M на данном слове.

Машина Тьюринга M
S={S0, S1,…,Sm} – внешний алфавит МТ M.
S0 = ‘Λ’ (пустой символ)
Q={q0, q1,…,qr} – внутренние состояния МТ M.
q1 – начальное состояние МТ M.
q0 – заключительное состояние МТ M.

Предикатные формулы
C(t,i,j) = “В момент времени t в ячейке i ленты МТ M находится символ Sj”.
H(t,i) = “В момент времени t обозревается ячейка i ленты МТ M”.
S(t,k) = “В момент времени t МТ M находится во внутреннем состоянии qk”.

Предикатные формулы
T(t) = “t является моментом времени”.
Nx(t,s) = “s следует непосредственно за t”.
Аксиомы:
1) T(0) & ∀s[T(s) ⊃ ¬ Nx(s,0)]– существует некоторый начальный момент времени t = 0.
2) T(t)⊃∃s(T(s)&Nx(t,s))&∀s1∀s2[T(s1)&T(s2)& &Nx(t, s1)&Nx(t, s2) ⊃(s1=s2)] – для каждого момента времени существует единственный следующий.

Предикатные формулы
3) T(t1)&T(t2)&T(s)&Nx(t1,s)& Nx(t2,s)
⊃(t1= t2)
4) (Nx(t,s) ⊃ Nx*(t,s)) &
(Nx*(t,s)& Nx*(s,r) ⊃ Nx*(t,r))&¬ Nx*(t,t))
– моменты времени идут последовательно друг за другом, т.е. невозможна ситуация:

Предикатные формулы
Sq(x) = “x является ячейкой ленты”.
L(x,y) = “x находится непосредственно слева от y”.
Аксиомы:
1) Sq(1)&…&Sq(n)&L(1,2)&…&L(n-1,n) – существуют идущие друг за другом ячейки, в которых содержится начальное слово.

Предикатные формулы
2) Sq(x)⊃∃y(Sq(y)&L(x,y))&∀y1∀y2[Sq(y1)&
&Sq(y2)&L(x, y1)&L(x, y2) ⊃(y1=y2)] – для каждой ячейки существует единственная ячейка, находящаяся справа от нее.
Sq(x)⊃∃y(Sq(y)&L(y,x))&∀y1∀y2[Sq(y1)&
&Sq(y2)&L(y1,x)&L(y2,x) ⊃(y1=y2)] – для каждой ячейки существует единственная ячейка, находящаяся слева от нее.

Предикатные формулы
3) (L(x,y) ⊃ L*(x,y)) &
(L*(x,y) & L*(y,z) ⊃ L*(x,z)) &
¬L*(x,x)

Характеристики МТ
1. В каждый момент времени головка обозревает ровно одну ячейку (= A).
2. В каждый момент времени в каждой ячейке ленты МТ стоит ровно один символ (= B).
3. В каждый момент времени МТ находится ровно в одном состоянии (= C).
4. При переходе от одного момента времени к другому может изменяться только содержимое обозреваемой ячейки (= D).

Характеристики МТ
5. Изменение состояния, положения головки и содержимого ячейки при переходе от одного момента времени к другому происходит в соответствии с программой МТ (= E).
6. Нулевой момент времени является начальным (= F).
7. Существует некоторый заключительный момент времени (= G).

Построение формулы A
A = ∀t (T(t) ⊃ At(t)),
где At(t) = “В момент времени t головка обозревает ровно одну клетку”.
At(t) =
∃i(Sq(i)& H(t,i))
&∀x∀y{(Sq(x)&Sq(y))⊃[(x=y)
∨ ¬(H(t,x)&H(t,y))]}

Построение формулы B
B = ∀t∀i [(T(t)&Sq(i)) ⊃ Bti(t,i)],
где Bti(t,i) = “В момент времени t в i-й ячейке ленты ровно один символ”.
Bti(t,i) =

Построение формулы C
C = ∀t (T(t) ⊃ Ct(t)),
где Ct(t) = “В момент времени t МТ находится ровно в одном состоянии”.
Сt(t) =

Построение формулы D
i
Sj2
Sj4
Sj3
Sj1
t
t′

Построение формулы E
Программа МТ состоит из инструкций вида {qiSjSkLqm}, {qiSjSkRqm}, {qiSjSkNqm}.
⊃ [C(t′,x,k)&
qi
qm
t
t′
&S(t′,m)]}

Построение формул F и G
F = S(0,1)&H(0,1)&
&C(0,1,Sj1)&…&C(0,n,Sjn)&∀i(Sq(i)⊃
[(i=1)∨…∨(i=n)∨C(0,i,0)])
G = ∃t′ S(t′,0)

Построение формулы U(M)
U(M)=A&B&C&D&E&F&G,
т.е. формула U(M) соответствует МТ M, удовлетворяющей приведенным ранее характеристикам.

Лемма 1
Если МТ M останавливается, то U(M) выполнима.

Лемма 2
Если U(M) выполнима, то МТ M останавливается.

Доказательство леммы 1
МТ M по определению удовлетворяет первым шести характеристикам, т.е. можно найти такое присвоение значений 0 и 1 предикатным формулам H, S, C и т.д., что формулы A, B, C, D, E, F истинны.
По условию леммы МТ M останавливается, т.е. в некоторый момент времени t′ приходит в заключительное состояние q0. Следовательно, формула G истинна.
Тогда формула U(M) тоже истинна.

Доказательство леммы 2
Если мы в выполнимой формуле в предикатные формулы подставим некоторые значения, мы получим истинное высказывание. В частности, если мы подставим значения в формулу U(M), мы получим истинное предложение
“В некоторый момент времени МТ M останавливается”.

Доказательство неразрешимости
Предположим, что исчисление предикатов разрешимо. Тогда существует машина Тьюринга для определения выполнимости U(M). По леммам 1 и 2 получаем, что существует машина, определяющая остановится ли машина M. Это невозможно. Следовательно, исчисление предикатов неразрешимо!