Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Обратная связь

Презентация на тему Машины Тьюринга

Содержание

2. § 6.1. Неформальное и
3. Было предложено много других формализаций
4. Основная модель (см. рис. 6.1)
5. Каждая ячейка может содержать ровно
6. q0∈QКонечное управлениеδ: Q × Γ → Q × (Γ \ {B}) × {L, R}ЛентаРис. 6.1.Yai∈ΣXi∈Γ
7. В один такт, зависящий от
8. Определение 6.1. Машина Тьюринга
9. Заметим, что если головка
10. Мы не позволили Tm
17. Два других случая, когда Tm останавливается,
18. Пример 6.1. Построим Tm, распоз-нающую
19. 2. а) δ(q1, 0) = (q1, 0, R); б)
20. 3. а) δ(q2, Y) = (q2, Y, L); б)
21. 4. а) δ(q4, 0) = (q4, 0, L) б)
22. 5. а) δ(q3, Y) = (q3, Y, R) б)
23. 6. Во всех случаях, кроме 1–5, функция
24. Таблица 6.1
25. § 6.2. Методы построения машин Тьюринга
26. § 6.3. Машина Тьюринга как процедура
27. Машина Тьюринга в примере 6.1
28. Следует подчеркнуть, что существуют языки,
29. Когда машина Тьюринга рассматри-вается как
30. Есть процедуры, для которых не
31. К каждой цепочке эта машина Тьюринга применяет
32. Имеет место факт, что не
33. § 6.4. Модификации машин Тьюринга
34. 6.4.1. Машина Тьюринга с бесконечной
35. 6.4.2. Многоленточная машина Тьюринга состоит
36. При одном движении, зависящем от
37. Теорема 6.2. Если язык L
38. 6.4.3. Недетерминированная машина Тьюринга есть устройство с
39. Теорема 6.3. Если язык L
40. Тогда любая последовательность вариан-тов движений
41. Можно построить детерминированную машину Тьюринга
42. Для каждой последовательности цифр,
43. Если машина T1 входит в
44. Скачать презентацию
45. Похожие презентации

§ 6.1. Неформальное и формальное описания В этой главе мы рассмотрим еще один тип распознающих устройств — машины Тьюринга. Это абстрактное устройство было предложено в качестве математической модели для описания

Было предложено много других формализаций процедуры, и было показано, что

Основная модель (см. рис. 6.1) имеет конечное управление, ленту, которая

Каждая ячейка может содержать ровно один из конечного числа символов

$q0∈QКонечное управлениеδ: Q × Γ → Q × (Γ \ {B}) × {L, R}ЛентаРис. 6.1.Yai∈ΣXi∈Γ$ В один такт, зависящий от символа, сканируемого головкой ленты, и

Определение 6.1. Машина Тьюринга (Tm) является формальной системой: T

Заметим, что если головка ленты покидает ячейку, она должна

Мы не позволили Tm печатать пробел ради простоты определения

Два других случая, когда Tm останавливается, однако, не принимая: когда значение

Пример 6.1. Построим Tm, распоз-нающую cfl L = {0n1n |

2. а) δ(q1, 0) = (q1, 0, R); б) δ(q1, Y) = (q1, Y,

3. а) δ(q2, Y) = (q2, Y, L); б) δ(q2, X) = (q3, X,

4. а) δ(q4, 0) = (q4, 0, L) б) δ(q4, X) = (q0, X,

5. а) δ(q3, Y) = (q3, Y, R) б) δ(q3, B) = (q5, Y,

6. Во всех случаях, кроме 1–5, функция δ не определена. Рассмотрим

§ 6.2. Методы построения машин Тьюринга Машина Тьюринга может “програм-мироваться” во

§ 6.3. Машина Тьюринга как процедура До сих пор мы определяли

Машина Тьюринга в примере 6.1 используется как распознаватель. Заметим, что

Следует подчеркнуть, что существуют языки, которые принимаются машинами Тьюринга, не

Когда машина Тьюринга рассматри-вается как процедура и оказывается, что она

Есть процедуры, для которых не существует никакого соответствующего алгоритма.

К каждой цепочке эта машина Тьюринга применяет алгоритм, данный в гл. 2,

Имеет место факт, что не существует машины Тьюринга, которая останавли-вается

§ 6.4. Модификации машин Тьюринга Одна из причин, по

6.4.1. Машина Тьюринга с бесконечной лентой в

6.4.2. Многоленточная машина Тьюринга состоит из конечного управления с k

При одном движении, зависящем от состояния конечного управления и сканируемого

Теорема 6.2. Если язык L принимается многоленточной машиной Тьюринга, то

6.4.3. Недетерминированная машина Тьюринга есть устройство с конечным управлением и одной бесконечной

Теорема 6.3. Если язык L принимается недетерминированной машиной Тьюринга T1,

Тогда любая последовательность вариан-тов движений конечной длины может быть представлена

Можно построить детерминированную машину Тьюринга T2, моделирующую машину T1. Снабдим

Для каждой последовательности цифр, сгенерированной на ленте 2, машина

Если машина T1 входит в принимающее состояние, то машина T2

Заметим, что это доказательство можно обобщить, чтобы показать, как моделиро-вать

Слайды презентации

Слайд 2 § 6.1. Неформальное и

§ 6.1. Неформальное и формальное описания В этой главе

формальное описания
В этой главе мы рассмотрим

еще один тип распознающих устройств — машины Тьюринга. Это абстрактное устройство было предложено в качестве математической модели для описания процедур. Так как наше интуитивное понятие процедуры как конечной последовательности инструкций, которые могут выполняться механически, не является математически точным, мы не можем доказать формально, что оно эквивалентно точному понятию машины Тьюринга.

Слайд 3 Было предложено много других формализаций процедуры,

и было показано, что все они эквивалентны формализации машины

Тьюринга.
А.Чёрчем была высказана гипотеза, что любой процесс, который естественным образом мог бы быть назван процедурой, реализуем машиной Тьюринга. Впоследствии вычислимость при помощи машины Тьюринга стала общепризнанным определением процедуры.
В литературе определение машины Тьюринга давалось разными способами. Мы начнем с обсуждения основной модели.

Слайд 4
Основная модель (см. рис. 6.1) имеет

конечное управление, ленту, которая раз-делена на ячейки, и головку

ленты, которая сканирует одну ячейку ленты зараз. Лента имеет крайнюю левую ячейку, но простирается в бесконечность в правую сторону.

Слайд 5 Каждая ячейка может содержать ровно один

из конечного числа символов ленты. Первоначально n крайних левых

ячеек для некоторого конечного n содержит входную цепочку, строку символов ленты, называе-мых входными символами.
Остальные ячейки до бесконечности содержат пробел — специальный символ ленты, который не считается входным символом.

Слайд 6
q0∈Q
Конечное управление
δ: Q × Γ → Q ×

$q0∈QКонечное управлениеδ: Q × Γ → Q × (Γ \ {B}) × {L, R}ЛентаРис. 6.1.Yai∈ΣXi∈Γ$

(Γ \ {B}) × {L, R}

Лента

Рис. 6.1.
Y
ai∈Σ
Xi∈Γ

Слайд 7 В один такт, зависящий от символа,

сканируемого головкой ленты, и состояния конечного управления, машина Тьюринга
1)

изменяет состояние;
2) печатает символ ленты, не являющийся пробелом, в сканируемой ячейке ленты, замещая то, что было там записано;
3) сдвигает свою головку влево или вправо на одну ячейку.

Слайд 8 Определение 6.1. Машина Тьюринга (Tm)

является формальной системой:
T = (Q, Σ, Γ, δ,

q0, F),
где Q — конечное множество состояний;
— конечное множество допустимых символов ленты, один из них, обычно обозначаемый буквой B, есть пробел;
⊆ Γ \ {B} — множество входных символов;
δ: Q × Γ → Q × (Γ \ {B}) × {L, R} — функция следующего такта (движения), для некоторых аргументов может быть не определена;
q0 ∈ Q — начальное состояние;
F ⊆ Q — множество конечных состояний.

Слайд 9 Заметим, что если головка ленты

покидает ячейку, она должна напечатать непустой символ в этой

ячейке, так что лента всегда содержит непустой блок символов с бесконечным числом пробелов справа от него.

Слайд 10 Мы не позволили Tm печатать

пробел ради простоты определения конфигураций. Однако, Tm могла бы

иметь другой символ, который трактуется точно так же, как пробел, за исключением того, что Tm разрешается печатать этот символ псевдопробела.
Разумеется, никакой дополнительной мощности не появляется за счёт введения такого символа.
В неформальном обсуждении мы часто допускаем печать пробела, зная, что вместо него можно использовать другой, но эквивалентный ему символ.

Слайд 11

Слайд 12

Слайд 13

Слайд 14

Слайд 15

Слайд 16

Слайд 17 Два других случая, когда Tm останавливается, однако,

Два других случая, когда Tm останавливается, однако, не принимая: когда

не принимая:
когда значение δ(q, X) при некоторых q∈Q

и X∈Γ не определено или
когда головка ленты “соскакивает” с левого конца ленты (позиция головки ленты i = 1 и задано движение влево).

Слайд 18 Пример 6.1. Построим Tm, распоз-нающую cfl

L = {0n1n | n ≥ 1}.

Положим T = (Q, Σ, Γ, δ, q0, F),
где Q ={q0, q1, q2, q3, q4, q5};
Σ = {0, 1}; Γ = {0, 1, B, X, Y}; F = {q5}.
Функцию δ определим следующим образом:
1. δ(q0, 0) = (q1, X, R).
В состоянии q0 символ 0 заменяется на X и машина сдвигается вправо в состояние q1 в поисках 1.

Ret 27

Слайд 19 2. а) δ(q1, 0) = (q1, 0, R);
б) δ(q1,

2. а) δ(q1, 0) = (q1, 0, R); б) δ(q1, Y) = (q1,

Y) = (q1, Y, R);
в) δ(q1, 1) = (q2,

Y, L).
Оставаясь в состоянии q1, машина продвигается вправо сквозь все нули (п. 2а) и блок Y (п. 2б). Наткнувшись на 1, заменяет её на Y и переходит в состояние q2, начав движение влево (п. 2в).

Слайд 20 3. а) δ(q2, Y) = (q2, Y, L);
б) δ(q2,

3. а) δ(q2, Y) = (q2, Y, L); б) δ(q2, X) = (q3,

X) = (q3, X, R);
в) δ(q2, 0) = (q4,

0, L).
Оставаясь в состоянии q2, машина продвигается влево сквозь блок Y (п. 3а).
Если машина встречает X, все еще оставаясь в состоянии q2, то больше нет нулей, которые следовало бы заменять на X, и машина переходит в состояние q3, начиная движение вправо, чтобы убедиться, что не осталось единиц (п. 3б).
Если же 0 встретился, машина переходит в состояние q4, чтобы продолжить движение в поисках крайнего левого 0 (п. 3в).

Слайд 21 4. а) δ(q4, 0) = (q4, 0, L)
б) δ(q4,

4. а) δ(q4, 0) = (q4, 0, L) б) δ(q4, X) = (q0,

X) = (q0, X, R).
Машина движется сквозь нули (п.

4а). Если встретился X, то машина прошла самый левый нуль. Она должна, сдвинувшись вправо, превратить этот 0 в X (п. 4б). Происходит переход в состояние q0, и процесс, только что описанный в п. 1–4, продолжается.

Слайд 22 5. а) δ(q3, Y) = (q3, Y, R)
б) δ(q3,

5. а) δ(q3, Y) = (q3, Y, R) б) δ(q3, B) = (q5,

B) = (q5, Y, R).
Машина входит в состояние q3,

когда ни одного 0 не остается (см. п. 3б). Машина должна продвигаться вправо (п. 5а) сквозь блок Y. Если встречается пробел раньше, чем 1, то ни одной 1 не осталось (п. 5б). В этой ситуации машина переходит в конечное состояние q5 и останавливается, сигнализируя тем самым прием входной цепочки.

Слайд 23 6. Во всех случаях, кроме 1–5, функция δ

не определена.
Рассмотрим действия машины Тьюринга на входной

цепочке 000111.
В табл. 6.1 приведены конфигурации в виде цепочек символов ленты с маркером состояния под сканируемым символом (в конфигурациях 25 и 26 маркер состояния находится под невидимым символом пробела).

Слайд 24 Таблица 6.1

Слайд 25 § 6.2. Методы построения
машин Тьюринга
Машина

Тьюринга может “програм-мироваться” во многом так же, как программируются

вычислительные маши-ны. Роль программы играет функция δ.
В параграфе § 6.2 Пособия представлена коллекция приемов программирования машины Тьюринга, которые помогут лучше узнать её возможности.

Слайд 26 § 6.3. Машина Тьюринга
как процедура
До

сих пор мы определяли машину Тьюринга как распознающее устройство.

Но можно рассматривать машину Тьюринга и как процедуру.
Например, если мы желаем описать процедуру для определения того, является ли число простым, мы могли бы построить машину Тьюринга, которая принимает множество всех простых чисел. Рассматриваем мы эту машину в данном случае как распознаватель или как процедуру — дело вкуса.

Слайд 27 Машина Тьюринга в примере 6.1 используется

как распознаватель. Заметим, что на некоторых входных цепочках, эта

машина со временем достигнет условия, при котором для состояния конечного управления и сканируемого символа функция δ не определена. В таком случае машина Тьюринга останавливается и никакие дальнейшие её движения невозможны.
Если язык принимается машиной Тьюринга, которая останавливается на всех входных цепочках, то говорят, что язык рекурсивен.

Слайд 28 Следует подчеркнуть, что существуют языки, которые

принимаются машинами Тьюринга, не останавливающимися для некоторых цепочек, не

содержащихся в языке, но которые не принимаются ни какими машинами Тьюринга, останавливаю-щимися на всех входных цепочках.
Язык, который может быть распознан некоторой машиной Тьюринга, называется рекурсивно перечислимым множеством (recursively enumerable set — res).

Слайд 29 Когда машина Тьюринга рассматри-вается как процедура

и оказывается, что она останавливается для всех входных цепочек,

то говорят, что такая процедура есть алгоритм.
В следующей главе будет показано, что рекурсивно перечислимые множества являются в точности языками, порож-даемыми грамматиками типа 0.

Слайд 30 Есть процедуры, для которых не существует

никакого соответствующего алгоритма.
Примером является процедура для

определения, порождает ли контекстно-зависимая грамматика (csg), по крайней мере, одну терминальную цепочку.
Можно построить машину Тьюринга, которая по заданной csg будет порождать все возможные терминальные цепочки в некотором лексикографическом порядке.

Слайд 31 К каждой цепочке эта машина Тьюринга применяет алгоритм,

К каждой цепочке эта машина Тьюринга применяет алгоритм, данный в гл.

данный в гл. 2, чтобы увидеть, порождается ли данная

цепочка грамматикой.
Если эта грамматика порождает хотя бы одно слово, машина найдет его и остановится в конечном состоянии.
Но если язык, порождаемый этой грамматикой, пуст, то машина будет продолжать порождать слова и проверять их вечно.

Слайд 32 Имеет место факт, что не существует

машины Тьюринга, которая останавли-вается на всех входных цепочках и

определяет для каждой csg, является ли язык, порождаемый этой грамматикой, пустым.
Другими словами, проблема распозна-вания непустоты контекстно-зависимого языка алгоритмически неразрешима.

Слайд 33 § 6.4. Модификации машин Тьюринга

Одна из причин, по которой машины Тьюринга принимаются

в качестве общей модели вычисления, состоит в том, что модель, с которой мы имеем дело, инвариантна по отношению ко многим модификациям, которые, казалось бы, увеличивают вычислительную мощность устройства.

Слайд 34 6.4.1. Машина Тьюринга с бесконечной

6.4.1. Машина Тьюринга с бесконечной лентой в обе стороны

лентой в обе стороны
Теорема 6.1. Если

язык L распознается машиной Тьюринга с бесконечной в обе стороны лентой, то он распознается машиной Тьюринга с полубесконечной лентой.

Слайд 35 6.4.2. Многоленточная машина Тьюринга состоит из

конечного управления с k ленточными головками, по одной на

каждой ленте.
Каждая лента бесконечна в обоих направлениях. Сначала входная цепоч-ка имеется только на первой ленте, а все другие ленты пусты.

Модификации машин Тьюринга

Слайд 36 При одном движении, зависящем от состояния

конечного управления и сканируемого символа каждой из ленточных головок,

машина может:
1) изменить состояние;
2) напечатать новый символ на каждой из сканируемых ячеек;
3) передвинуть каждую из её ленточных головок независимо друг от друга на одну ячейку влево, вправо или оставить её на том же самом месте.

Слайд 37 Теорема 6.2. Если язык L принимается

многоленточной машиной Тьюринга, то он принимается одноленточной машиной Тьюринга.

Слайд 38 6.4.3. Недетерминированная машина Тьюринга есть устройство с конечным

6.4.3. Недетерминированная машина Тьюринга есть устройство с конечным управлением и одной

управлением и одной бесконечной в обе стороны лентой. Для

данного состояния и ленточного символа, сканируемого головкой ленты, машина имеет несколько вариантов для следующего движения. Каждый вариант состоит из нового состояния, ленточного символа, который печатается, и направления движения головки. Недетерминированная машина Тьюринга принимает входную цепочку, если какая-нибудь последовательность вариантов движений приводит к принимающему состоянию.

Слайд 39 Теорема 6.3. Если язык L принимается

недетерминированной машиной Тьюринга T1, то он принимается некоторой детерми-нированной

машиной Тьюринга T2.
Доказательство. Для любого состояния и ленточного символа машины T1 имеется конечное число вариантов для выбора следующего движения. Варианты могут быть занумерованы числами 1, 2, ... .
Пусть r — максимальное число вариантов для любой пары состояние — ленточный символ.

Слайд 40 Тогда любая последовательность вариан-тов движений конечной

длины может быть представлена последовательностью цифр от 1 до

r.
Не все такие последовательности могут представлять варианты движений, посколь-ку в некоторых конфигурациях вариантов может быть меньше, чем r.

Слайд 41 Можно построить детерминированную машину Тьюринга T2,

моделирующую машину T1. Снабдим её тремя лентами.

Лента 1 будет содержать входную цепочку.
На ленте 2 машина T2 будет системати-чески генерировать последовательность “цифр” от 1 до r, начиная с самой короткой. Среди последовательностей одинаковой длины они генерируются в числовом порядке.

Слайд 42 Для каждой последовательности цифр, сгенерированной

на ленте 2, машина T2 копирует вход на ленту

3 и затем моделирует машину T1 на ленте 3, используя последовательность ленты 2 для того, чтобы диктовать движения машины T1.

Слайд 43 Если машина T1 входит в принимающее

состояние, то машина T2 также принимает.
Если

имеется последовательность вариантов, ведущая к приёму, то она в конце концов будет сгенерирована на ленте 2.
Машина T2 , как модель T1, тоже будет принимать входную цепочку.
Но если никакая последовательность вариантов движений машины T1 не ведёт к приёму входной цепочки, то машина T2 тоже не примет её.