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

Сентябрь 13, 2022

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

Содержание

2. Проблема разрешимости Существует ли алгоритм, позволяющий установить, выполнима данная формула U исчисления предикатов или нет?
3. ИСЧИСЛЕНИЕ ПРЕДИКАТОВ НЕРАЗРЕШИМО
4. Доказательство Для произвольной машины Тьюринга M мы построим формулу U(M) и покажем, что если существует метод
5. Машина Тьюринга M S={S0, S1,…,Sm} – внешний алфавит МТ M. S0 = ‘Λ’ (пустой символ) Q={q0,
6. Предикатные формулы C(t,i,j) = “В момент времени t в ячейке i ленты МТ M находится символ
7. Предикатные формулы T(t) = “t является моментом времени”. Nx(t,s) = “s следует непосредственно за t”. Аксиомы:
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))&¬
9. Предикатные формулы Sq(x) = “x является ячейкой ленты”. L(x,y) = “x находится непосредственно слева от y”.
10. Предикатные формулы 2) Sq(x)⊃∃y(Sq(y)&L(x,y))&∀y1∀y2[Sq(y1)& &Sq(y2)&L(x, y1)&L(x, y2) ⊃(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. В
13. Характеристики МТ 5. Изменение состояния, положения головки и содержимого ячейки при переходе от одного момента времени
14. Построение формулы A A = ∀t (T(t) ⊃ At(t)), где At(t) = “В момент времени t
15. Построение формулы B B = ∀t∀i [(T(t)&Sq(i)) ⊃ Bti(t,i)], где Bti(t,i) = “В момент времени t
16. Построение формулы C C = ∀t (T(t) ⊃ Ct(t)), где Ct(t) = “В момент времени t
17. Построение формулы D i Sj2 Sj4 Sj3 Sj1 t t′
18. Построение формулы E Программа МТ состоит из инструкций вида {qiSjSkLqm}, {qiSjSkRqm}, {qiSjSkNqm}. ⊃ [C(t′,x,k)& qi qm
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)]) G = ∃t′ S(t′,0)
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 по определению удовлетворяет первым шести характеристикам, т.е. можно найти такое присвоение
24. Доказательство леммы 2 Если мы в выполнимой формуле в предикатные формулы подставим некоторые значения, мы получим
25. Доказательство неразрешимости Предположим, что исчисление предикатов разрешимо. Тогда существует машина Тьюринга для определения выполнимости U(M). По
27. Скачать презентацию

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

Слайд 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))]}

Слайд 15

Построение формулы B
B = ∀t∀i [(T(t)&Sq(i)) ⊃ Bti(t,i)],
где Bti(t,i)

= “В момент времени t в i-й ячейке ленты ровно один символ”.

Bti(t,i) =

Слайд 16

Построение формулы C
C = ∀t (T(t) ⊃ Ct(t)),
где Ct(t)

= “В момент времени t МТ находится ровно в одном состоянии”.

Сt(t) =

Слайд 17

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

Слайд 18

Построение формулы E
Программа МТ состоит из инструкций вида {qiSjSkLqm}, {qiSjSkRqm},

{qiSjSkNqm}.

⊃ [C(t′,x,k)&

t′

&S(t′,m)]}

Слайд 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)])
G = ∃t′

S(t′,0)

Слайд 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. Это невозможно. Следовательно, исчисление предикатов неразрешимо!

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

Содержание

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

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

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

Машина Тьюринга MS={S0, S1,…,Sm} – внешний алфавит МТ M.S0 = ‘Λ’

Предикатные формулы C(t,i,j) = “В момент времени t в ячейке i

Предикатные формулыT(t) = “t является моментом времени”.Nx(t,s) = “s следует непосредственно

Предикатные формулы3) T(t1)&T(t2)&T(s)&Nx(t1,s)& Nx(t2,s) ⊃(t1= t2) 4) (Nx(t,s) ⊃ Nx*(t,s))

Предикатные формулыSq(x) = “x является ячейкой ленты”.L(x,y) = “x находится непосредственно

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

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

Характеристики МТ 1. В каждый момент времени головка обозревает ровно одну

Характеристики МТ 5. Изменение состояния, положения головки и содержимого ячейки при

Построение формулы A A = ∀t (T(t) ⊃ At(t)), где At(t)

Построение формулы B B = ∀t∀i [(T(t)&Sq(i)) ⊃ Bti(t,i)], где Bti(t,i)

Построение формулы C C = ∀t (T(t) ⊃ Ct(t)), где Ct(t)

Построение формулы DiSj2Sj4Sj3Sj1tt′

Построение формулы E Программа МТ состоит из инструкций вида {qiSjSkLqm}, {qiSjSkRqm},

Построение формул F и GF = 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′

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

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

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

Доказательство леммы 1 МТ M по определению удовлетворяет первым шести характеристикам,

Доказательство леммы 2 Если мы в выполнимой формуле в предикатные формулы

Доказательство неразрешимости Предположим, что исчисление предикатов разрешимо. Тогда существует машина Тьюринга

Похожие презентации