2 (1108001)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Курс «Алгоритмы и алгоритмические языки»1 семестр 2015/2016Лекция 2Машина Тьюринга (МТ)Алфавит состояний Q = {q0, q1, q2, …, qn}Рабочий алфавит S = A  A':A – алфавит входных символов,A' – алфавит вспомогательных символов (маркеров).Лента, размеченная на ячейки (пустая ячейка - )Управляющая головка (УГ)Рабочая ячейка (РЯ)Начальное состояние q0, состояние останова qs.Начальные данные – слова из A*.2Машина Тьюринга (МТ)...0010111001011100000...qКонфигурация МТ: n, F, q, где F: Z  SТакт работы МТ:состояние, символ  состояние, символ, направление3Машина Тьюринга (МТ)Нормальные МТ.Любую МТ можно перестроить таким образом, что она будет, вычисляяту же функцию, удовлетворять следующим двум условиям:(1) в начальном состоянии (q0) УГ установлена напротив пустой ячейки,которая следует за всеми исходными символами:...(()())((()))...q0(2) в состоянии останова (qs) УГ установлена напротив пустой ячейки,которая следует за всеми символами результата:...1...qsМТ, удовлетворяющая условиям (1) и (2), называется нормальной МТ.4Диаграммы Тьюринга (ДТ)Перестройка МТ к виду, более удобному для ДТ(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|-15Диаграммы Тьюринга (ДТ)Перестройка МТ к виду, более удобному для ДТ(1) МТ с лентой, ограниченной с левого конца(a)перегнем ленту по ячейке с номером 0;(б)раздвинем ячейки правой части ленты(с неотрицательными номерами), помещаясодержимое ячейки с номером n в ячейку с номером 2n(в)в освободившиеся ячейки с нечетными номерамипоместим содержимое ячеек левой части ленты(с отрицательными номерами), помещая содержимоеячейки с номером n в ячейку с номером 2|n|-10123450 -11 -22 -3bcdak673 -4a89 10 11 12 …4 -5f5 -66 … …q06Диаграммы Тьюринга (ДТ)Перестройка МТ к виду, более удобному для ДТ(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)вправона двевправона двевлевона двевправона однувлевовлевона двевлевона двевправона однувправона двевправо7Диаграммы Тьюринга (ДТ)Перестройка МТ к виду, более удобному для ДТ(2) МТ с укороченными инструкциями.Рассмотрим произвольную инструкцию МТ T:q, a  q', b, R;Разобьем ее на две инструкции:(1) q, a  q'', b, H (только записывает символ в РЯ);(2) q'', b  q', b, R (только сдвигает головку).Можно доказать, что для любой МТ T можно построить МТ T', каждаяинструкция которой либо только сдвигает головку, либо толькозаписывает символ в РЯ.МТ T' и есть МТ с укороченными инструкциями.8Диаграммы Тьюринга (ДТ)Перестройка МТ к виду, более удобному для ДТДалее будем рассматривать класс МТ, который содержит только МТ сукороченными инструкциями, лентой, ограниченной слева,выполняющие нормальные вычисления по Тьюрингу.Все эти предположения не являются ограничением общности, так какпо произвольной МТ нетрудно построить МТ рассматриваемого класса.Основным преимуществом рассматриваемого класса МТ являетсявозможность ввести понятие действия.vij={L, R, H, siS}9Диаграммы Тьюринга (ДТ)Построение диаграмм ТьюрингаЗапись символа в РЯ или сдвиг УГ вправо или влево называютсяэлементарными действиями.МТ, выполняющие элементарные действияЭлементарная МТПрограмма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10Диаграммы Тьюринга (ДТ)Построение диаграмм ТьюрингаПримеры не элементарных МТ.×L=×l ××R=××r ××МТ L переводит конфигурацию[...a1a2a3...an...q0в конфигурацию[...a1a2a3...an...q1(1)В дальнейшем слово на ленте a1a2a3...an будем обозначать w, т.е.

(1)будем записывать в виде [...w...q111Диаграммы Тьюринга (ДТ)Построение диаграмм ТьюрингаМТ 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.можно использовать диаграмму МТ K12Диаграммы Тьюринга (ДТ)Построение таблиц по диаграммам(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 ;Перепишем все таблицы одну за другой (в любойпоследовательности)13Диаграммы Тьюринга (ДТ)Построение таблиц по диаграммамЗамечание.

Диаграмма каждой МТ начинается и заканчивается точкой(начальное состояние и состояние останова). При композициидиаграмм конечная точка диаграммы сливается с начальной точкойследующей диаграммы и тем самым исключается. Следовательно,у каждой диаграммы остается только одна точка (начальная).(5)Добавим в таблицу следующие строки:(а)для каждого символа A, которому соответствуетстрелка, ведущая из точки снова к ней же,добавим строку q0A  Aq0(б)для каждого символа A, которому соответствуетстрелка, ведущая из точки к символу M, добавимстроку q0A  AqM0(в)для каждого символа A, которому не соответствуетникакая стрелка, ведущая из точки, добавим строкуq0A  hqs14Диаграммы Тьюринга (ДТ)Построение таблиц по диаграммам(5)(г)если два символа M и M′ соединены стрелкой, надкоторой надписан символ a, то всякую строку qa  hq′для состояния останова q из части таблицы,соответствующей M, заменяем строкой qa  aqM′0(аналогично для стрелки в состояние останова)В результате преобразований (1) – (5) получится таблица МТ, котораявыполняет те же действия, что и МТ, заданная диаграммой.Поэтому МТ, задаваемые диаграммами, эквивалентны МТ,задаваемыми таблицами.15Диаграммы Тьюринга (ДТ)Моделирование МТОпределение.

МТ M моделирует МТ M′, если выполнены следующиеусловия:(1)Данная начальная конфигурация вызывает машинный остановМТ M после конечного числа шагов тогда и только тогда, когдауказанная начальная конфигурация вызывает машинныйостанов МТ M ′ после конечного числа шагов(2)Данная начальная конфигурация вызывает переход за крайленты у МТ M после конечного числа шагов тогда и толькотогда, когда указанная начальная конфигурация вызываетпереход за край ленты у МТ M ′ после конечного числа шагов(3)Последовательность текущих конфигураций МТ M ′ для даннойначальной конфигурации является подпоследовательностьюпоследовательности текущих конфигураций МТ M для той женачальной конфигурации16.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций