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

Нажмите для полного просмотра!

Неразрешимость исчисления предикатов, слайд №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 исчисления предикатов или нет?

Слайд 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 головка обозревает ровно одну клетку”.

Слайд 15

Описание слайда:

Построение формулы 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 МТ находится ровно в одном состоянии”.

Слайд 17

Описание слайда:

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

Слайд 18

Описание слайда:

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

Слайд 19

Описание слайда:

Построение формул F и G

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