Презентация Неразрешимость исчисления предикатов онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Неразрешимость исчисления предикатов абсолютно бесплатно. Урок-презентация на эту тему содержит всего 26 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:26 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:280.50 kB
- Просмотров:54
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№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))&s1s2[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))&y1y2[Sq(y1)&
&Sq(y2)&L(x, y1)&L(x, y2) (y1=y2)] – для каждой ячейки существует единственная ячейка, находящаяся справа от нее.
Sq(x)y(Sq(y)&L(y,x))&y1y2[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 = ti [(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 – предикатный символ)
Тогда получим доказательство для чистого ИП.
Скачать все slide презентации Неразрешимость исчисления предикатов одним архивом:
