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

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

2. Проблема разрешимости

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

3.

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

4. Доказательство

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

5. Машина Тьюринга M

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

6. Предикатные формулы

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

7. Предикатные формулы

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)] – для каждого
момента времени существует единственный
следующий.

8. Предикатные формулы

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))
– моменты времени идут последовательно
друг за другом, т.е. невозможна
ситуация:
t1
s
t2

9. Предикатные формулы

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

10. Предикатные формулы

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)] – для
каждой ячейки существует единственная
ячейка, находящаяся слева от нее.

11. Предикатные формулы

3) (L(x,y) L*(x,y)) &
(L*(x,y) & L*(y,z) L*(x,z)) &
¬L*(x,x)

12. Характеристики МТ

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

13. Характеристики МТ

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

14. Построение формулы 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))]}
t
i
t
x=y
t
x
y

15. Построение формулы B

B = t i [(T(t)&Sq(i)) Bti(t,i)],
где Bti(t,i) = “В момент времени t в i-й
ячейке ленты ровно один символ”.
Bti(t,i) =
j:S j S
C(t,i,j) & x y{(x=y) (C(t,i,x)&C(t,i,y))}
t
i
Sj

16. Построение формулы C

C = t (T(t) Ct(t)),
где Ct(t) = “В момент времени t МТ
находится ровно в одном состоянии”.
Сt(t) =
k :qk Q
S(t,k) & x y{(x=y)
t
i
Sj
qk
(S(t,x)&S(t, y))}

17. Построение формулы D

D = t t i j{(T(t)&T(t )&Nx(t,t )&Sq(i))
[H(t,i) (C(t,i,j) C(t ,i,j))]}
tt
i
Sj1 Sj2
j4 Sj3

18. Построение формулы E

Программа МТ состоит из инструкций вида
{qiSjSkLqm}, {qiSjSkRqm}, {qiSjSkNqm}.
E = t t x y1 y2 i j{[T(t)&T(t )&Nx(t,t )&Sq(x)&
&Sq(y1)&Sq(y2)&L(y1,x)&L(x,y2)&H(t,x)&C(t,x,j)&S(t,i)]
H(t ,y )
1
[C(t ,x,k)& H(t ,y2) &S(t ,m)]}
H(t ,x)
t
y1 x y2
Skj
qqmi

19. Построение формул 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)])
1
n
Sj1 … Sjn
q1
i
G = t S(t ,0)
t=0
t
Sj
q0

20. Построение формулы U(M)

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

21. Лемма 1

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

22. Лемма 2

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

23. Доказательство леммы 1

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

24. Доказательство леммы 2

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

25. Доказательство неразрешимости

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

26. Чистое ИП

x=y заменим предикатом Eq(x,y), для которого
определим аксиомы:
1) Eq(x,x).
2) (Eq(x,y)&Eq(y,z)) Eq(x,z).
3) Eq(x,y) Eq(y,x).
4) Eq(x1,y1)&…& Eq(xn,yn)
(P(x1,…,xn) P(y1,…,yn)) для каждого
введенного предиката (P – предикатный символ)
Тогда получим доказательство для чистого ИП.