03 (1106240)

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

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

Курс «Алгоритмы и алгоритмические языки»1 семестр 2013/2014Лекция 31Диаграммы Тьюринга (ДТ)Универсальная машина ТьюрингаЭтапы построения УМТ.(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.2Диаграммы Тьюринга (ДТ)Универсальная машина ТьюрингаЭтапы построения УМТ.(3) Как происходит интерпретация моделируемой МТ?(a)УМТ “запоминает” (размножением состояний)обозреваемый в ячейке символ aj из Ap и заменяет его на bj.(б)УМТ ищет слово программы wi, описывающее текущеесостояние моделируемой МТ (отмечено звездочкой).(в)УМТ ищет символ bj, соответствующий “запомненному”на шаге а) символу aj, и сдвигается вправо через действие vij доописания сдвига на следующее состояние моделируемой МТ.wiaj[cw0cw1…*b0vi0++…bjvij–…bpvipO…cws§at1at2…bj…atwΛΛ...q3Диаграммы Тьюринга (ДТ)Универсальная машина ТьюрингаЭтапы построения УМТ.(3) Как происходит интерпретация моделируемой МТ?(г)УМТ передвигает символ обозначения текущегосостояния моделируемой МТ (звездочку) по описанию сдвига наее символ с и возвращается на описание действия vij.(д)УМТ ищет записанный на шаге а) символ bj из данныхмоделируемой МТ (после символа §) и выполняет считанноедействие (запись или сдвиг).Замечание.

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

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

МТ T называетсясамоприменимой, если она останавливается, когда в качественачальных данных используется описание T – слово надалфавитом S∪ Q.Существует ли МТ, которая по описанию МТ распознает,самоприменима ли она?Алгоритмическая неразрешимость проблемысамоприменимости следует из свойств МТ E и E* спредыдущего слайда.8Нормальные алгоритмы МарковаОпределение нормального алгоритма Маркова (НАМ)V – алфавит основных символовV′ – алфавит маркеровσ, σ′ ∈ (V ∪V′)*Подстановка: σ →σ′ переводитслово τ = ασβ ∈ (V∪ V′)* в слово τ′ = ασ′β ∈ (V∪ V')*подслова α и β могут быть пустыми (ε)Помимо символов алфавита V∪ V' в подстановках используютсяметасимволы «→» (стрелка) отделяет левую часть подстановки отправой и «.» (точка) отмечает терминальную подстановку9Нормальные алгоритмы МарковаОпределение.

Нормальный алгоритм Маркова (НАМ) задаетсяконечной последовательностью подстановок { p1,p 2, … p n } .При этом:(1)если применимо несколько подстановок, применяетсяподстановка, которая встречается в описании алгоритмараньше других;(2)если подстановка применима к нескольким подсловамобрабатываемого слова, выбирается самое левое подслово;(3)после применения терминальной подстановки алгоритмзавершается;(4)если ни одна из подстановок неприменима, алгоритмзавершается.10Нормальные алгоритмы МарковаПример НАМ. Шифр Юлия Цезаря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)→ FDHVDU11Нормальные алгоритмы МарковаПроцедура интерпретации НАМ(1)Положить i = 0.(2)Положить j = 1.(3)Если правило pj применимо к σi , перейти к шагу (5).(4)(5)Положить j = j + 1.

Если j ≤ n, то перейти к шагу (3).В противном случае – остановка.Применить pj к σi и найти σi+1. Положить i = i + 1.Если pj – нетерминальное правило, то перейти к 2.В противном случае – остановка.Говорят, что НАМ применим к слову σ0, если в результате произойдетостановка.Терминальное правило содержит метасимвол . (точка).Иногда вместо →. используется метасимвол12Нормальные алгоритмы МарковаПример. Сложение чисел в единичной системе счисления:V = { +, | }, V' = { }.Правила подстановок: { | + → + |; + | → |; | →. | }Пример применения алгоритма:(1)«| | | | + | | + | | |» = «| | | | + | | + | | |» ⇒ «| | | + | | | + | | |»(1)(1)(1)(1)⇒ «| | + | | | | + | | |» ⇒ «| + | | | | | + | | |»(1)⇒ «+ | | | | | | + | | |» ⇒ «+ | | | | | + | | | |» ⇒ …(1)( 2)(2)⇒ «+ + | | | | | | | | |»⇒ «+ | | | | | | | | |» ⇒ «| | | | | | | | |» ⇒( 3)Первое правило «перегоняет» плюсы налево до упора, второе правилоих «стирает», третье правило «убеждается», что плюсов не осталось.13Нормальные алгоритмы МарковаЗаключительные замечанияТезис Маркова.

Любой алгоритм в алфавите V может бытьпредставлен нормальным алгоритмом Маркова над алфавитомV.Примерно так же, как и для МТ, можно доказатьалгоритмическую неразрешимость проблемы останова исамоприменимости.Существуют различные НАМ решения одной и той же задачи.Проблема построения алгоритма, который может определитьэквивалентность любых двух НАМ, алгоритмическинеразрешима.Можно построить универсальный НАМ U, который мог быинтерпретировать любой нормальный алгоритм, включаясамого себя.14Заключительные замечанияМожно доказать эквивалентность двух формальных системТьюринга и Маркова конструктивным путем: построитьуниверсальную МТ, которая могла бы интерпретировать любойНАМ и, наоборот, построить универсальный НАМ, которыйинтерпретирует любую МТ.Существуют и другие формальные описания алгоритмов:машина Поста, λ-исчисление, рекурсивные функции и др.Для всех таких формальных систем доказана ихэквивалентность МТ.МТ невозможно реализовать на конечной машине: МТ с лентойконечных размеров не обеспечивает реализации всехалгоритмов.Тезис Тьюринга – Черча (основная гипотеза теорииалгоритмов).

Для любой интуитивно вычислимой функциисуществует вычисляющая её значения МТ.15Критика модели вычислений ТьюрингаМедленная (неускоряемая)частые копирования данных: у нормальных МТ каждоенеэлементарное действие выполняется над крайнимиправыми словами лентыотказ от нормальных вычислений приведет кпостоянному поиску данных и усложнит алгоритмчисло состояний МТ часто зависит от числа символовв алфавите МТ16.

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

Тип файла PDF

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

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

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