Презентация «Неразрешимость исчисления предикатов»
Смотреть слайды в полном размере 
Вы можете ознакомиться с презентацией онлайн, просмотреть текст и слайды к ней, а также, в случае, если она вам подходит - скачать файл для редактирования или печати. Документ содержит 26 слайдов и доступен в формате ppt. Размер файла: 280.50 KB
Pic.1
Неразрешимость исчисления предикатов
Pic.2
Проблема разрешимости Существует ли алгоритм, позволяющий установить, выполнима данная формула U исчисления предикатов или нет?
Pic.3
ИСЧИСЛЕНИЕ ПРЕДИКАТОВ НЕРАЗРЕШИМО
Pic.4
Доказательство Для произвольной машины Тьюринга M мы построим формулу U(M) и покажем, что если существует метод определения, выполнима ли U(M), то существует метод определения, остановится ли МТ M на …
Pic.5
Машина Тьюринга M S={S0, S1,…,Sm} – внешний алфавит МТ M. S0 = ‘Λ’ (пустой символ) Q={q0, q1,…,qr} – внутренние состояния МТ M. q1 – начальное состояние МТ M. q0 – заключительное состояние МТ M.
Pic.6
Предикатные формулы C(t,i,j) = “В момент времени t в ячейке i ленты МТ M находится символ Sj”. H(t,i) = “В момент времени t обозревается ячейка i ленты МТ M”. S(t,k) = “В момент времени t МТ M …
Pic.7
Предикатные формулы T(t) = “t является моментом времени”. Nx(t,s) = “s следует непосредственно за t”. Аксиомы: 1) T(0) & s[T(s) Nx(s,0)]– существует некоторый начальный момент времени t = 0. …
Pic.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)) – моменты времени идут …
Pic.9
Предикатные формулы Sq(x) = “x является ячейкой ленты”. L(x,y) = “x находится непосредственно слева от y”. Аксиомы: 1) Sq(1)&…&Sq(n)&L(1,2)&…&L(n-1,n) – существуют идущие друг за …
Pic.10
Предикатные формулы 2) Sq(x)y(Sq(y)&L(x,y))&y1y2[Sq(y1)& &Sq(y2)&L(x, y1)&L(x, y2) (y1=y2)] – для каждой ячейки существует единственная ячейка, находящаяся справа от нее. …
Pic.11
Предикатные формулы 3) (L(x,y) L*(x,y)) & (L*(x,y) & L*(y,z) L*(x,z)) & ¬L*(x,x)
Pic.12
Характеристики МТ 1. В каждый момент времени головка обозревает ровно одну ячейку (= A). 2. В каждый момент времени в каждой ячейке ленты МТ стоит ровно один символ (= B). 3. В каждый момент времени …
Pic.13
Характеристики МТ 5. Изменение состояния, положения головки и содержимого ячейки при переходе от одного момента времени к другому происходит в соответствии с программой МТ (= E). 6. Нулевой момент …
Pic.14
Построение формулы A A = t (T(t) At(t)), где At(t) = “В момент времени t головка обозревает ровно одну клетку”.
Pic.15
![Построение формулы B B = ti [(T(t)&Sq(i)) Bti(t,i)], где Bti(t,i) = “В момент времени t в i-](/documents_6/cbc125a2ef0a328ab740f80b9dc608a4/img14.jpg)
Построение формулы B B = ti [(T(t)&Sq(i)) Bti(t,i)], где Bti(t,i) = “В момент времени t в i-й ячейке ленты ровно один символ”.
Pic.16
Построение формулы C C = t (T(t) Ct(t)), где Ct(t) = “В момент времени t МТ находится ровно в одном состоянии”.
Pic.17
Построение формулы D
Pic.18
Построение формулы E Программа МТ состоит из инструкций вида {qiSjSkLqm}, {qiSjSkRqm}, {qiSjSkNqm}.
Pic.19
Построение формул F и G
Pic.20
Построение формулы U(M) U(M)=A&B&C&D&E&F&G, т. е. формула U(M) соответствует МТ M, удовлетворяющей приведенным ранее характеристикам.
Pic.21
Лемма 1 Если МТ M останавливается, то U(M) выполнима.
Pic.22
Лемма 2 Если U(M) выполнима, то МТ M останавливается.
Pic.23
Доказательство леммы 1 МТ M по определению удовлетворяет первым шести характеристикам, т. е. можно найти такое присвоение значений 0 и 1 предикатным формулам H, S, C и т. д. , что формулы A, B, C, D, …
Pic.24
Доказательство леммы 2 Если мы в выполнимой формуле в предикатные формулы подставим некоторые значения, мы получим истинное высказывание. В частности, если мы подставим значения в формулу U(M), мы …
Pic.25
Доказательство неразрешимости Предположим, что исчисление предикатов разрешимо. Тогда существует машина Тьюринга для определения выполнимости U(M). По леммам 1 и 2 получаем, что существует машина, …
Pic.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) …
Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!
