3 (1108002)

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

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

Курс «Алгоритмы и алгоритмические языки»1 семестр 2015/2016Лекция 31Диаграммы Тьюринга (ДТ)Моделирование МТОпределение. МТ M моделирует МТ M′, если выполнены следующиеусловия:(1)Данная начальная конфигурация вызывает машинный остановМТ M после конечного числа шагов тогда и только тогда, когдауказанная начальная конфигурация вызывает машинныйостанов МТ M ′ после конечного числа шагов(2)Данная начальная конфигурация вызывает переход за крайленты у МТ M после конечного числа шагов тогда и толькотогда, когда указанная начальная конфигурация вызываетпереход за край ленты у МТ M ′ после конечного числа шагов(3)Последовательность текущих конфигураций МТ M ′ для даннойначальной конфигурации является подпоследовательностьюпоследовательности текущих конфигураций МТ M для той женачальной конфигурации2Диаграммы Тьюринга (ДТ)Универсальная машина ТьюрингаОпределение. Универсальной машиной Тьюринга (УМТ) для алфавитаAp называется такая МТ U, на которой может быть промоделированалюбая МТ над алфавитом Ap.Замечание.

На самом деле можно эффективно построить УМТ,моделирующую любую МТ над любым алфавитом. Для этогофиксируется некоторый алфавит (например A2 = {0,1}) и добавляетсякодирование и декодирование.Идея УМТ. На ленту УМТ записывается программа моделируемой МТ(таблица) и исходные данные моделируемой МТ. УМТ по состоянию итекущему символу МТ находит на своей ленте команду моделируемойМТ, выясняет, какое действие нужно выполнить, и выполняет его.3Диаграммы Тьюринга (ДТ)Универсальная машина ТьюрингаЭтапы построения УМТ.(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 ijb v i k , если k  i j ij(2) Как выглядит лента в исходном состоянии УМТ?[*w0cw1…cws§w...qw – исходные данные моделируемой МТ.

Звездочка отмечает q0.4Диаграммы Тьюринга (ДТ)Универсальная машина ТьюрингаЭтапы построения УМТ.(3) Как происходит интерпретация моделируемой МТ?(a)УМТ “запоминает” (размножением состояний)обозреваемый в ячейке символ aj из Ap и заменяет его на bj.(б)УМТ ищет слово программы wi, описывающее текущеесостояние моделируемой МТ (отмечено звездочкой).(в)УМТ ищет символ bj, соответствующий “запомненному”на шаге а) символу aj, и сдвигается вправо через действие vij доописания сдвига на следующее состояние моделируемой МТ.wiaj[cw0cw1…*b0vi0++…bjvij–…bpvipO…cws§at1at2…bj…atw...q5Диаграммы Тьюринга (ДТ)Универсальная машина ТьюрингаЭтапы построения УМТ.(3) Как происходит интерпретация моделируемой МТ?(г)УМТ передвигает символ обозначения текущегосостояния моделируемой МТ (звездочку) по описанию сдвига наее символ с и возвращается на описание действия vij.(д)УМТ ищет записанный на шаге а) символ bj из данныхмоделируемой МТ (после символа §) и выполняет считанноедействие (запись или сдвиг).Замечание.

Если при сдвиге УГ попала на символ §, отделяющийпрограмму моделируемой МТ от данных, это означает, чтомоделируемая МТ зашла за левый край ленты.(е)Снова можно выполнять шаг а).6Диаграммы Тьюринга (ДТ)Универсальная машина ТьюрингаЭтапы построения УМТ.(4) Как происходит останов УМТ?Если на шаге 3 б) при поиске слова wi был найден символ § (справапосле звездочки), моделируемая МТ находится в состоянии останова.(а)УМТ ищет символ bj из данных моделируемой МТ(после символа §) и записывает запомненный символ aj.(б)После этого УГ УМТ указывает на ячейку, на которойдолжна остановиться УГ моделируемой МТ.[cw0cw1…*ws§МТ(w)...q7Машина Тьюринга (МТ)Проблема останова.

Существует ли алгоритм, определяющий,произойдет ли когда-либо останов МТ T на входных данных w?(для любых машин T и любых входных данных)(другая формулировка) Остановится ли УМТ, моделирующая МТ T навходных данных w?Утверждение. Проблема останова алгоритмически неразрешима.8Машина Тьюринга (МТ)Проблема останова.Пусть существует машина D, решающая проблему остановадля всех МТ T и входных данных w. Построим машину E,которая по данной МТ T запускает машину D для МТ T изаписи (описания) T на ленте.Машина E*:lrДаE* = .EНет.Останавливается ли машина E*, если ее применить кописанию самой себя?9Машина Тьюринга (МТ)Проблема самоприменимостиРассмотрим МТ T для алфавита Ap.

МТ T называетсясамоприменимой, если она останавливается, когда в качественачальных данных используется описание T – слово надалфавитом S Q.Существует ли МТ, которая по описанию МТ распознает,самоприменима ли она?Алгоритмическая неразрешимость проблемысамоприменимости следует из свойств МТ E и E* спредыдущего слайда.10Нормальные алгоритмы МарковаОпределение нормального алгоритма Маркова (НАМ)V – алфавит основных символовV′ – алфавит маркеров, ′  (V V′)*Подстановка:  ′ переводитслово  =   (V V′)* в слово ′ = ′  (V V')*подслова  и  могут быть пустыми ()Помимо символов алфавита V V' в подстановках используютсяметасимволы «» (стрелка) отделяет левую часть подстановки отправой и «.» (точка) отмечает терминальную подстановку11Нормальные алгоритмы МарковаОпределение.

Нормальный алгоритм Маркова (НАМ) задаетсяконечной последовательностью подстановок { p1,p2, … pn }.При этом:(1)если применимо несколько подстановок, применяетсяподстановка, которая встречается в описании алгоритмараньше других;(2)если подстановка применима к нескольким подсловамобрабатываемого слова, выбирается самое левое подслово;(3)после применения терминальной подстановки алгоритмзавершается;(4)если ни одна из подстановок неприменима, алгоритмзавершается.12Нормальные алгоритмы МарковаПример НАМ. Шифр Юлия ЦезаряV = {a, b, c, …, z}, V' = {*}.j-ая буква латинского алфавита шифруется j+h (mod 26)-ой буквойтого же алфавита.Например, для h = 3 подстановки имеют вид(маркер * помечает текущую шифруемую букву, цифра в скобках –номер правила подстановки):(1) *A  D*, (2) *B  E*, (3) *C  F*, …,(23) *W  Z*, (24) *X  A*, (25) *Y  B*,(26) *Z  C*, (27) * .

, (28)  *Применим построенный НАМ к слову CAESAR:CAESAR (28) *CAESAR (3) F*AESAR (1) FD*ESAR (5)FDH*SAR (13) FDHV*AR (1) FDHVD*R (12)FDHVDU* (27) FDHVDU13.

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

Тип файла PDF

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

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

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