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

U исчисления предикатов или нет?

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

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

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

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

Nx*(t,s)) &
(Nx*(t,s)& Nx*(s,r) ⊃ Nx*(t,r))&¬ Nx*(t,t))
– моменты времени идут последовательно друг за другом, т.е. невозможна ситуация:

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

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

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

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

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

где 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))]}

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

Bti(t,i) =

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

Сt(t) =

{qiSjSkRqm}, {qiSjSkNqm}.

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

qi

qm

t

t′

&S(t′,m)]}

S(t′,0)

приведенным ранее характеристикам.

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

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

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

аксиомы:
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 – предикатный символ)
Тогда получим доказательство для чистого ИП.