Слайды лекций - 2014 (лектор - Белеванцев А. А.) (1107979), страница 2
Текст из файла (страница 2)
Проверка правильности скобочных выражений:МТ должна записать на ленту для правильного скобочного выражениярезультат 1 (для неправильного 0) и остановиться.Рабочий алфавит: S = {(, ), 0, 1} ∪ {Λ, X} (X – маркер)Алфавит состояний Q = {q0, q1, q2, q3, qs}:q0 – начальное состояние МТ: поиск закрывающей скобки;qs – состояние останова;q1 – поиск парной открывающей скобки;q2 – стирание маркеров, запись результата 1 и переход в qs;q3 – стирание маркеров, запись результата 0 и переход в qs.В начальном состоянии УГ обозревает самый левыйсимвол входного слова18Машина Тьюринга (МТ)Пример. Проверка правильности скобочных выражений:МТ должна записать на ленту для правильного скобочного выражениярезультат 1 (для неправильного 0) и остановиться.Программаq0, ( → q0, (, R;q0, ) → q1, X, L;q0, X → q0, X, R;q0, Λ → q2, Λ, L;q1, ( → q0, X, R;q1, ) → q1, ), L;q1, X → q1, X, L;q1, Λ → q3, Λ, R;q2, ( → q3, Λ, L;q2, ) невозможна;q2, X → q2, Λ, L;q2, Λ → qs, 1, H;q3, ( → q3, Λ, R;q3, ) невозможна;q3, X → q3, Λ, R;q3, Λ → qs, 0, H;19Машина Тьюринга (МТ)Пример.
Проверка правильности скобочных выражений:МТ должна записать на ленту для правильного скобочного выражениярезультат 1 (для неправильного 0) и остановиться.Программа (другой способ записи)qi ↓ \ sj →q0q1q2q3(q0, (, Rq0, X, Rq3, Λ, Lq3, Λ, R)q1, X, Lq1, ), L——XΛq0, X, R q2, Λ, Lq1, X, L q3, Λ, Rq2, Λ, L qs, 1, Hq3, Λ, R qs, 0, H20Машина Тьюринга (МТ)Нормальные МТ.Любую МТ можно перестроить таким образом, что она будет, вычисляяту же функцию, удовлетворять следующим двум условиям:(1) в начальном состоянии (q0) УГ установлена напротив пустой ячейки,которая следует за всеми исходными символами:...ΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛ(()())((()))ΛΛΛΛΛΛΛΛΛΛΛΛ...q0(2) в состоянии останова (qs) УГ установлена напротив пустой ячейки,которая следует за всеми символами результата:...ΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛ1ΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛ...qsМТ, удовлетворяющая условиям (1) и (2), называется нормальной МТ.21Диаграммы Тьюринга (ДТ)Перестройка МТ к виду, более удобному для ДТ(1) МТ с лентой, ограниченной с левого концаДля произвольной МТ T с неограниченной лентой построимМТ T' с лентой, ограниченной с левого конца, которая работаеттак же… -5 -4 -3 -2 -1 0 1 2 3 4 5 6 …… Λ(a)(б)(в)ΛΛkabcdafΛΛ…q0перегнем ленту по ячейке с номером 0;раздвинем ячейки правой части ленты, помещаясодержимое ячейки с номером n в ячейку с номером 2⋅nв освободившиеся ячейки с нечетными номерамипоместим содержимое ячеек левой части ленты,помещая содержимое ячейки с номером n в ячейкус номером 2⋅|n|-122Диаграммы Тьюринга (ДТ)Перестройка МТ к виду, более удобному для ДТ(1) МТ с лентой, ограниченной с левого конца(a)перегнем ленту по ячейке с номером 0;(б)раздвинем ячейки правой части ленты(с неотрицательными номерами), помещаясодержимое ячейки с номером n в ячейку с номером 2⋅n(в)в освободившиеся ячейки с нечетными номерамипоместим содержимое ячеек левой части ленты(с отрицательными номерами), помещая содержимоеячейки с номером n в ячейку с номером 2⋅|n|-10123450 -11 -22 -3bcdakΛ673 -4aΛ89 10 11 12 …4 -5fΛ5 -66 …ΛΛ …Λq023Диаграммы Тьюринга (ДТ)Перестройка МТ к виду, более удобному для ДТ(1) МТ с лентой, ограниченной с левого концаT… -5 -4 -3 -2 -1 0 1 2 3 4 5 6 ……ΛΛΛkabcdafΛΛ …0123456q0T′край ленты0 -11 -22 -3bcdakΛ783 -4a9 10 11 12 …4 -5ΛfΛ5 -66 …ΛΛ …Λq0TT′T′T′T′(четные)(нечетные)(ячейка 0)(ячейка 1)вправона двевправона двевлевона двевправона однувлевовлевона двевлевона двевправона однувправона двевправо24Диаграммы Тьюринга (ДТ)Перестройка МТ к виду, более удобному для ДТ(2) МТ с укороченными инструкциями.Рассмотрим произвольную инструкцию МТ T:q, a → q', b, R;Разобьем ее на две инструкции:(1) q, a → q'', b, H (только записывает символ в РЯ);(2) q'', b → q', b, R (только сдвигает головку).Можно доказать, что для любой МТ T можно построить МТ T', каждаяинструкция которой либо только сдвигает головку, либо толькозаписывает символ в РЯ.МТ T' и есть МТ с укороченными инструкциями.25Диаграммы Тьюринга (ДТ)Перестройка МТ к виду, более удобному для ДТДалее будем рассматривать класс МТ, который содержит только МТ сукороченными инструкциями, лентой, ограниченной слева,выполняющие нормальные вычисления по Тьюрингу.Все эти предположения не являются ограничением общности, так какпо произвольной МТ нетрудно построить МТ рассматриваемого класса.Основным преимуществом рассматриваемого класса МТ являетсявозможность ввести понятие действия.vij={L, R, H, si∈S}26Диаграммы Тьюринга (ДТ)Построение диаграмм ТьюрингаЗапись символа в РЯ или сдвиг УГ вправо или влево называютсяэлементарными действиями.МТ, выполняющие элементарные действияЭлементарная МТПрограммаlq0 Λ → l q1, q0 a1 → l q1, …, q0 ap → l q1,rq0 Λ → r q1,…, q0 ap → rq1,aiq0 Λ → ai q1, q0 a1 → ai q1, …, q0 ap → ai q1,q1 – состояние останова*q1 – состояние останова*q1 – состояние останова**Иногда пишут правила вида q1 ai → hqsДиаграмма⋅l⋅⋅ r⋅⋅ai⋅27Диаграммы Тьюринга (ДТ)Построение диаграмм ТьюрингаПримеры не элементарных МТ.≠Λ≠ΛL=⋅ l⋅ΛR=⋅⋅ r⋅Λ⋅МТ L переводит конфигурацию[ΛΛ...Λa1a2a3...anΛΛ...q0в конфигурацию[ΛΛ...Λa1a2a3...anΛΛ...q1(1)В дальнейшем слово на ленте a1a2a3...an будем обозначать w, т.е.
(1)будем записывать в виде [ΛΛ...ΛwΛΛ...q128Диаграммы Тьюринга (ДТ)Построение диаграмм ТьюрингаМТ K переводит конфигурацию :[Λ Λ … Λ w Λ Λ …q0т.е.в конфигурацию :[Λ Λ … Λ w Λ w Λ Λ …qsкопирует слово w. Диаграмма МТ K (над алфавитом {0,1})Λ→R→R→0→L→L→ 0r 1 Λ→R→R→1→L→L→ 1Λ0K = .LR.Соглашение: стрелочки, над которыми ничего не надписано, опускаются.Получаем упрощенную диаграмму:Левая точка соответствует состоянию q0,20L20правая – состоянию qsR0В дальнейшем при построении новых МТK = .L r 1 R21L21ΛΛΛR.можно использовать диаграмму МТ K29Курс «Алгоритмы и алгоритмические языки»1 семестр 2014/2015Лекция 31Диаграммы Тьюринга (ДТ)Построение таблиц по диаграммам(1)Заменяем упрощенную диаграмму полной(2)С помощью индексации добиваемся, чтобы каждый символ МТвходил в диаграмму только один раз.K = .L1Λ1→R1→R2→01→L2→L3→ 02r0 1 Λ →R →R →1 →L →L → 12341452Λ0R5 .(3)Сопоставим каждому символу МТ ее таблицу.
Например, МТ r0сопоставим таблицу: q00Λ→ r q01; q000→ r q01 ; q001→ r q01 ;q01Λ→(4)h q0s; q010→ h q0s ; q011→ h q0s ;Перепишем все таблицы одну за другой (в любойпоследовательности)2Диаграммы Тьюринга (ДТ)Построение таблиц по диаграммамЗамечание. Диаграмма каждой МТ начинается и заканчивается точкой(начальное состояние и состояние останова).
При композициидиаграмм конечная точка диаграммы сливается с начальной точкойследующей диаграммы и тем самым исключается. Следовательно,у каждой диаграммы остается только одна точка (начальная).(5)Добавим в таблицу следующие строки:(а)для каждого символа A, которому соответствуетстрелка, ведущая из точки снова к ней же,добавим строку q0A → Aq0(б)для каждого символа A, которому соответствуетстрелка, ведущая из точки к символу M, добавимстроку q0A → AqM0(в)для каждого символа A, которому не соответствуетникакая стрелка, ведущая из точки, добавим строкуq0A → hqs3Диаграммы Тьюринга (ДТ)Построение таблиц по диаграммам(5)(г)если два символа M и M′ соединены стрелкой, надкоторой надписан символ a, то всякую строку qa → hq′для состояния останова q из части таблицы,соответствующей M, заменяем строкой qa → aqM′0(аналогично для стрелки в состояние останова)В результате преобразований (1) – (5) получится таблица МТ, котораявыполняет те же действия, что и МТ, заданная диаграммой.Поэтому МТ, задаваемые диаграммами, эквивалентны МТ,задаваемыми таблицами.4Диаграммы Тьюринга (ДТ)Моделирование МТОпределение.
МТ M моделирует МТ M′, если выполнены следующиеусловия:(1)Данная начальная конфигурация вызывает машинный остановМТ M после конечного числа шагов тогда и только тогда, когдауказанная начальная конфигурация вызывает машинныйостанов МТ M ′ после конечного числа шагов(2)Данная начальная конфигурация вызывает переход за крайленты у МТ M после конечного числа шагов тогда и толькотогда, когда указанная начальная конфигурация вызываетпереход за край ленты у МТ M ′ после конечного числа шагов(3)Последовательность текущих конфигураций МТ M ′ для даннойначальной конфигурации является подпоследовательностьюпоследовательности текущих конфигураций МТ M для той женачальной конфигурации5Диаграммы Тьюринга (ДТ)Универсальная машина ТьюрингаОпределение.
Универсальной машиной Тьюринга (УМТ) для алфавитаAp называется такая МТ U, на которой может быть промоделированалюбая МТ над алфавитом Ap.Замечание. На самом деле можно эффективно построить УМТ,моделирующую любую МТ над любым алфавитом. Для этогофиксируется некоторый алфавит (например A2 = {0,1}) и добавляетсякодирование и декодирование.Идея УМТ. На ленту УМТ записывается программа моделируемой МТ(таблица) и исходные данные моделируемой МТ. УМТ по состоянию итекущему символу МТ находит на своей ленте команду моделируемойМТ, выясняет, какое действие нужно выполнить, и выполняет его.6Диаграммы Тьюринга (ДТ)Универсальная машина ТьюрингаЭтапы построения УМТ.(1) Как представить программу моделируемой МТ на ленте УМТ?Рабочий алфавит A′ УМТ является расширением алфавита Ap.A′ = Ap ∪ {b1, b2, …, bp} ∪ {b0} ∪ {r, l, h, +, –,O, c, §,*}Программа: cw0cw1…cws§, где wi – слово-программа для qi.b j vij + k −i , если k > iПравило qiaj→vijqk, слово-правило: b v O , если k = i j ijb v −i −k , если k < i j ij(2) Как выглядит лента в исходном состоянии УМТ?[*w0cw1…cws§wΛΛ...qw – исходные данные моделируемой МТ.
Звездочка отмечает q0.7Диаграммы Тьюринга (ДТ)Универсальная машина ТьюрингаЭтапы построения УМТ.(3) Как происходит интерпретация моделируемой МТ?(a)УМТ “запоминает” (размножением состояний)обозреваемый в ячейке символ aj из Ap и заменяет его на bj.(б)УМТ ищет слово программы wi, описывающее текущеесостояние моделируемой МТ (отмечено звездочкой).(в)УМТ ищет символ bj, соответствующий “запомненному”на шаге а) символу aj, и сдвигается вправо через действие vij доописания сдвига на следующее состояние моделируемой МТ.wiaj[cw0cw1…*b0vi0++…bjvij–…bpvipO…cws§at1at2…bj…atwΛΛ...q8Диаграммы Тьюринга (ДТ)Универсальная машина ТьюрингаЭтапы построения УМТ.(3) Как происходит интерпретация моделируемой МТ?(г)УМТ передвигает символ обозначения текущегосостояния моделируемой МТ (звездочку) по описанию сдвига наее символ с и возвращается на описание действия vij.(д)УМТ ищет записанный на шаге а) символ bj из данныхмоделируемой МТ (после символа §) и выполняет считанноедействие (запись или сдвиг).Замечание.
Если при сдвиге УГ попала на символ §, отделяющийпрограмму моделируемой МТ от данных, это означает, чтомоделируемая МТ зашла за левый край ленты.(е)Снова можно выполнять шаг а).9Диаграммы Тьюринга (ДТ)Универсальная машина ТьюрингаЭтапы построения УМТ.(4) Как происходит останов УМТ?Если на шаге 3 б) при поиске слова wi был найден символ § (справапосле звездочки), моделируемая МТ находится в состоянии останова.(а)УМТ ищет символ bj из данных моделируемой МТ(после символа §) и записывает запомненный символ aj.(б)После этого УГ УМТ указывает на ячейку, на которойдолжна остановиться УГ моделируемой МТ.[cw0cw1…*ws§МТ(w)ΛΛ...q10Машина Тьюринга (МТ)Проблема останова.
Существует ли алгоритм, определяющий,произойдет ли когда-либо останов МТ T на входных данных w?(другая формулировка) Остановится ли УМТ, моделирующая МТ T навходных данных w?Утверждение. Проблема останова алгоритмически неразрешима.11Машина Тьюринга (МТ)Проблема останова.Пусть существует машина D, решающая проблему остановадля всех МТ T и входных данных w. Построим машину E,которая по данной МТ T запускает машину D для МТ T изаписи (описания) T на ленте.Машина E*:lrДаE* = .EНет.Останавливается ли машина E*, если ее применить кописанию самой себя?12Машина Тьюринга (МТ)Проблема самоприменимостиРассмотрим МТ T для алфавита Ap. МТ T называетсясамоприменимой, если она останавливается, когда в качественачальных данных используется описание T – слово надалфавитом S∪ Q.Существует ли МТ, которая по описанию МТ распознает,самоприменима ли она?Алгоритмическая неразрешимость проблемысамоприменимости следует из свойств МТ E и E* спредыдущего слайда.13Курс «Алгоритмы и алгоритмические языки»1 семестр 2014/2015Лекция 41Нормальные алгоритмы МарковаОпределение нормального алгоритма Маркова (НАМ)V – алфавит основных символовV′ – алфавит маркеровσ, σ′ ∈ (V ∪V′)*Подстановка: σ →σ′ переводитслово τ = ασβ ∈ (V∪ V′)* в слово τ′ = ασ′β ∈ (V∪ V')*подслова α и β могут быть пустыми (ε)Помимо символов алфавита V∪ V' в подстановках используютсяметасимволы «→» (стрелка) отделяет левую часть подстановки отправой и «.» (точка) отмечает терминальную подстановку2Нормальные алгоритмы МарковаОпределение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
