02 (1106239)
Текст из файла
Курс «Алгоритмы и алгоритмические языки»1 семестр 2013/2014Лекция 21Машина Тьюринга (МТ)Нормальные МТ.Любую МТ можно перестроить таким образом, что она будет, вычисляяту же функцию, удовлетворять следующим двум условиям:(1) в начальном состоянии (q0) УГ установлена напротив пустой ячейки,которая следует за всеми исходными символами:...ΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛ(()())((()))ΛΛΛΛΛΛΛΛΛΛΛΛ...q0(2) в состоянии останова (qs) УГ установлена напротив пустой ячейки,которая следует за всеми символами результата:...ΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛ1ΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛ...qsМТ, удовлетворяющая условиям (1) и (2), называется нормальной МТ.2Диаграммы Тьюринга (ДТ)Перестройка МТ к виду, более удобному для ДТ(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|-13Диаграммы Тьюринга (ДТ)Перестройка МТ к виду, более удобному для ДТ(1) МТ с лентой, ограниченной с левого конца(a)перегнем ленту по ячейке с номером 0;(б)раздвинем ячейки правой части ленты(с неотрицательными номерами), помещаясодержимое ячейки с номером n в ячейку с номером 2⋅n(в)в освободившиеся ячейки с нечетными номерамипоместим содержимое ячеек левой части ленты(с отрицательными номерами), помещая содержимоеячейки с номером n в ячейку с номером 2⋅|n|-10123450 -11 -22 -3bcdakΛ673 -4aΛ89 10 11 12 …4 -5fΛ5 -66 …ΛΛ …Λq04Диаграммы Тьюринга (ДТ)Перестройка МТ к виду, более удобному для ДТ(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)вправона двевправона двевлевона двевправона однувлевовлевона двевлевона двевправона однувправона двевправо5Диаграммы Тьюринга (ДТ)Перестройка МТ к виду, более удобному для ДТ(2) МТ с укороченными инструкциями.Рассмотрим произвольную инструкцию МТ T:q, a → q', b, R;Разобьем ее на две инструкции:(1) q, a → q'', b, H (только записывает символ в РЯ);(2) q'', b → q', b, R (только сдвигает головку).Можно доказать, что для любой МТ T можно построить МТ T', каждаяинструкция которой либо только сдвигает головку, либо толькозаписывает символ в РЯ.МТ T' и есть МТ с укороченными инструкциями.6Диаграммы Тьюринга (ДТ)Перестройка МТ к виду, более удобному для ДТДалее будем рассматривать класс МТ, который содержит только МТ сукороченными инструкциями, лентой, ограниченной слева,выполняющие нормальные вычисления по Тьюрингу.Все эти предположения не являются ограничением общности, так какпо произвольной МТ нетрудно построить МТ рассматриваемого класса.Основным преимуществом рассматриваемого класса МТ являетсявозможность ввести понятие действия.vij={L, R, H, si∈S}7Диаграммы Тьюринга (ДТ)Построение диаграмм ТьюрингаЗапись символа в РЯ или сдвиг УГ вправо или влево называютсяэлементарными действиями.МТ, выполняющие элементарные действияЭлементарная МТПрограмма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⋅8Диаграммы Тьюринга (ДТ)Построение диаграмм ТьюрингаПримеры не элементарных МТ.≠Λ≠ΛL=⋅ l⋅ΛR=⋅⋅ r⋅Λ⋅МТ L переводит конфигурацию[ΛΛ...Λa1a2a3...anΛΛ...q0в конфигурацию[ΛΛ...Λa1a2a3...anΛΛ...q1(1)В дальнейшем слово на ленте a1a2a3...an будем обозначать w, т.е.
(1)будем записывать в виде [ΛΛ...ΛwΛΛ...q19Диаграммы Тьюринга (ДТ)Построение диаграмм ТьюрингаМТ 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.можно использовать диаграмму МТ K10Диаграммы Тьюринга (ДТ)Построение таблиц по диаграммам(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 ;Перепишем все таблицы одну за другой (в любойпоследовательности)11Диаграммы Тьюринга (ДТ)Построение таблиц по диаграммамЗамечание. Диаграмма каждой МТ начинается и заканчивается точкой(начальное состояние и состояние останова). При композициидиаграмм конечная точка диаграммы сливается с начальной точкойследующей диаграммы и тем самым исключается.
Следовательно,у каждой диаграммы остается только одна точка (начальная).(5)Добавим в таблицу следующие строки:(а)для каждого символа A, которому соответствуетстрелка, ведущая из точки снова к ней же,добавим строку q0A → Aq0(б)для каждого символа A, которому соответствуетстрелка, ведущая из точки к символу M, добавимстроку q0A → AqM0(в)для каждого символа A, которому не соответствуетникакая стрелка, ведущая из точки, добавим строкуq0A → hqs12Диаграммы Тьюринга (ДТ)Построение таблиц по диаграммам(5)(г)если два символа M и M′ соединены стрелкой, надкоторой надписан символ a, то всякую строку qa → hq′для состояния останова q из части таблицы,соответствующей M, заменяем строкой qa → aqM′0(аналогично для стрелки в состояние останова)В результате преобразований (1) – (5) получится таблица МТ, котораявыполняет те же действия, что и МТ, заданная диаграммой.Поэтому МТ, задаваемые диаграммами, эквивалентны МТ,задаваемыми таблицами.13Диаграммы Тьюринга (ДТ)Моделирование МТОпределение.
МТ M моделирует МТ M′, если выполнены следующиеусловия:(1)Данная начальная конфигурация вызывает машинный остановМТ M после конечного числа шагов тогда и только тогда, когдауказанная начальная конфигурация вызывает машинныйостанов МТ M ′ после конечного числа шагов(2)Данная начальная конфигурация вызывает переход за крайленты у МТ M после конечного числа шагов тогда и толькотогда, когда указанная начальная конфигурация вызываетпереход за край ленты у МТ M ′ после конечного числа шагов(3)Последовательность текущих конфигураций МТ M ′ для даннойначальной конфигурации является подпоследовательностьюпоследовательности текущих конфигураций МТ M для той женачальной конфигурации14Диаграммы Тьюринга (ДТ)Универсальная машина ТьюрингаОпределение.
Универсальной машиной Тьюринга (УМТ) для алфавитаAp называется такая МТ U, на которой может быть промоделированалюбая МТ над алфавитом Ap.Замечание. На самом деле можно эффективно построить УМТ,моделирующую любую МТ над любым алфавитом. Для этогофиксируется некоторый алфавит (например A2 = {0,1}) и добавляетсякодирование и декодирование.Идея УМТ. На ленту УМТ записывается программа моделируемой МТ(таблица) и исходные данные моделируемой МТ. УМТ по состоянию итекущему символу МТ находит на своей ленте команду моделируемойМТ, выясняет, какое действие нужно выполнить, и выполняет его.15Диаграммы Тьюринга (ДТ)Универсальная машина ТьюрингаЭтапы построения УМТ.(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.16Диаграммы Тьюринга (ДТ)Универсальная машина ТьюрингаЭтапы построения УМТ.(3) Как происходит интерпретация моделируемой МТ?(a)УМТ “запоминает” (размножением состояний)обозреваемый в ячейке символ aj из Ap и заменяет его на bj.(б)УМТ ищет слово программы wi, описывающее текущеесостояние моделируемой МТ (отмечено звездочкой).(в)УМТ ищет символ bj, соответствующий “запомненному”на шаге а) символу aj, и сдвигается вправо через действие vij доописания сдвига на следующее состояние моделируемой МТ.wiaj[cw0cw1…*b0vi0++…bjvij–…bpvipO…cws§at1at2…bj…atwΛΛ...q17Диаграммы Тьюринга (ДТ)Универсальная машина ТьюрингаЭтапы построения УМТ.(3) Как происходит интерпретация моделируемой МТ?(г)УМТ передвигает символ обозначения текущегосостояния моделируемой МТ (звездочку) по описанию сдвига наее символ с и возвращается на описание действия vij.(д)УМТ ищет записанный на шаге а) символ bj из данныхмоделируемой МТ (после символа §) и выполняет считанноедействие (запись или сдвиг).Замечание.
Если при сдвиге УГ попала на символ §, отделяющийпрограмму моделируемой МТ от данных, это означает, чтомоделируемая МТ зашла за левый край ленты.(е)Снова можно выполнять шаг а).18Диаграммы Тьюринга (ДТ)Универсальная машина ТьюрингаЭтапы построения УМТ.(4) Как происходит останов УМТ?Если на шаге 3 б) при поиске слова wi был найден символ § (справапосле звездочки), моделируемая МТ находится в состоянии останова.(а)УМТ ищет символ bj из данных моделируемой МТ(после символа §) и записывает запомненный символ.(б)УМТ перемещается направо на первую пустую ячейкупосле конца слова-результата.[cw0cw1…*ws§МТ(w)ΛΛ...q19.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
