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

Категория: Математика
Нажмите для полного просмотра!
Неразрешимость исчисления предикатов, слайд №1Неразрешимость исчисления предикатов, слайд №2Неразрешимость исчисления предикатов, слайд №3Неразрешимость исчисления предикатов, слайд №4Неразрешимость исчисления предикатов, слайд №5Неразрешимость исчисления предикатов, слайд №6Неразрешимость исчисления предикатов, слайд №7Неразрешимость исчисления предикатов, слайд №8Неразрешимость исчисления предикатов, слайд №9Неразрешимость исчисления предикатов, слайд №10Неразрешимость исчисления предикатов, слайд №11Неразрешимость исчисления предикатов, слайд №12Неразрешимость исчисления предикатов, слайд №13Неразрешимость исчисления предикатов, слайд №14Неразрешимость исчисления предикатов, слайд №15Неразрешимость исчисления предикатов, слайд №16Неразрешимость исчисления предикатов, слайд №17Неразрешимость исчисления предикатов, слайд №18Неразрешимость исчисления предикатов, слайд №19Неразрешимость исчисления предикатов, слайд №20Неразрешимость исчисления предикатов, слайд №21Неразрешимость исчисления предикатов, слайд №22Неразрешимость исчисления предикатов, слайд №23Неразрешимость исчисления предикатов, слайд №24Неразрешимость исчисления предикатов, слайд №25Неразрешимость исчисления предикатов, слайд №26
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Неразрешимость исчисления предикатов. Доклад-сообщение содержит 26 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


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

Слайд 2


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

Слайд 3


ИСЧИСЛЕНИЕ ПРЕДИКАТОВ НЕРАЗРЕШИМО
Описание слайда:
ИСЧИСЛЕНИЕ ПРЕДИКАТОВ НЕРАЗРЕШИМО

Слайд 4


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

Слайд 5


Машина Тьюринга M S={S0, S1,…,Sm} – внешний алфавит МТ M. S0 = ‘Λ’ (пустой символ) Q={q0, q1,…,qr} – внутренние состояния МТ M. q1 – начальное состояние МТ M. q0 – заключительное состояние МТ M.
Описание слайда:
Машина Тьюринга 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”.
Описание слайда:
Предикатные формулы 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)] – для каждого момента времени существует единственный следующий.
Описание слайда:
Предикатные формулы 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)) – моменты времени идут последовательно друг за другом, т.е. невозможна ситуация:
Описание слайда:
Предикатные формулы 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) – существуют идущие друг за другом ячейки, в которых содержится начальное слово.
Описание слайда:
Предикатные формулы 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)] – для каждой ячейки существует единственная ячейка, находящаяся слева от нее.
Описание слайда:
Предикатные формулы 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)
Описание слайда:
Предикатные формулы 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).
Описание слайда:
Характеристики МТ 1. В каждый момент времени головка обозревает ровно одну ячейку (= A). 2. В каждый момент времени в каждой ячейке ленты МТ стоит ровно один символ (= B). 3. В каждый момент времени МТ находится ровно в одном состоянии (= C). 4. При переходе от одного момента времени к другому может изменяться только содержимое обозреваемой ячейки (= D).

Слайд 13


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

Слайд 14


Построение формулы A A = t (T(t)  At(t)), где At(t) = “В момент времени t головка обозревает ровно одну клетку”.
Описание слайда:
Построение формулы 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 в i-й ячейке ленты ровно один символ”.
Описание слайда:
Построение формулы B B = ti [(T(t)&Sq(i))  Bti(t,i)], где Bti(t,i) = “В момент времени t в i-й ячейке ленты ровно один символ”.

Слайд 16


Построение формулы C C = t (T(t)  Ct(t)), где Ct(t) = “В момент времени t МТ находится ровно в одном состоянии”.
Описание слайда:
Построение формулы C C = t (T(t)  Ct(t)), где Ct(t) = “В момент времени t МТ находится ровно в одном состоянии”.

Слайд 17


Построение формулы D
Описание слайда:
Построение формулы D

Слайд 18


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

Слайд 19


Построение формул F и G
Описание слайда:
Построение формул F и G

Слайд 20


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

Слайд 21


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

Слайд 22


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

Слайд 23


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

Слайд 24


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

Слайд 25


Доказательство неразрешимости Предположим, что исчисление предикатов разрешимо. Тогда существует машина Тьюринга для определения выполнимости U(M). По леммам 1 и 2 получаем, что существует машина, определяющая остановится ли машина M. Это невозможно. Следовательно, исчисление предикатов неразрешимо!
Описание слайда:
Доказательство неразрешимости Предположим, что исчисление предикатов разрешимо. Тогда существует машина Тьюринга для определения выполнимости 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 – предикатный символ) Тогда получим доказательство для чистого ИП.
Описание слайда:
Чистое ИП 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 – предикатный символ) Тогда получим доказательство для чистого ИП.

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию