Время работы алгоритма Дейкстры на машине Тьюринга

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Содержание

1. Машина Тьюринга

2. Палиндром

3. Реализация проверки палиндрома на машине Тьюринга

4. Время работы алгоритма Дейкстры на машине Тьюринга

Список литературы

1. Машина Тьюринга

Машина Тьюринга (МТ) - абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча - Тьюринга, способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.

Устройство машины Тьюринга

В состав машины Тьюринга входит полубесконечная лента (возможны машины Тьюринга, которые имеют несколько лент), разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.

Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.

Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма.

Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара «ленточный символ - состояние», для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной.

Описание машины Тьюринга

Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: q_ia_j>q_i1a_j1d_k (если головка находится в состоянии q_i, а в обозреваемой ячейке записана буква a_j, то головка переходит в состояние q_i1, в ячейку вместо a_j записывается a_j1, головка делает движение d_k, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (S)). Для каждой возможной конфигурации <q_i, a_j> имеется ровно одно правило (для недетерминированной машины Тьюринга может быть большее количество правил). Правил нет только для заключительного состояния (q₀), попав в которое машина останавливается.

2. Палиндром

Слово палинром, происходит от греч. рЬлйн - «назад, снова» и греч. дсумпт - «бег»), иногда также палиндромон, от гр. palindromos бегущий обратно) - число (например, 404), буквосочетание, слово (например, топот, фин. saippuakauppias = продавец мыла - самое длинное употребительное слово-палиндром в мире) или текст (а роза упала на лапу Азора), одинаково читающееся в обоих направлениях. Иногда палиндромом неформально называют любой симметричный относительно своей середины набор символов.

Отдельные палиндромические словосочетания и фразы известны с глубокой древности, когда им зачастую придавался магически-сакральный смысл (не лишена этого оттенка, например, фраза На в лоб, болван, использовавшаяся русскими скоморохами в качестве перформативного высказывания). Авторское творчество в области палиндрома начинается, по-видимому, в Средние века. В русской литературе достоверно известно об авторском палиндромном стихе Державина «Я имду съ мемчемъ судия», затем об авторском палиндромном стихе Фета «А роза упала на лапу Азора». Первую попытку многострочного (и довольно длинного) стихотворного произведения в форме палиндрома предпринял Велимир Хлебников в поэме «Разин». Однако расцвета русский литературный палиндром (преимущественно стихотворный) достиг только в 1970-1990-е года в творчестве Николая Ладыгина, а затем Владимира Гершуни, Елены Кацюбы и Дмитрия Авалиани. В 1990-х годах началось в России и детальное литературоведческое и лингвистическое изучение палиндромии - прежде всего Александром Бубновым и Германом Лукомниковым. Теоретики и практики палиндрома выделили многочисленные пограничные с палиндромом формы: например, оборотень - текст, читающийся слева направо иначе, чем справа налево: «Мир удобен» (Сергей Федин). Среди более редких разновидностей палиндромических текстов следует назвать также слоговые, словесные и фразовые палиндромы, двуязычные палиндромы (в одну сторону текст читается на одном языке, в обратную - на другом) и т.п.

Существуют разновидности, когда чтение производится не в обратном направлении, а в прямом, но с другого места в «размноженном» термине, например, кабанкабан, кольцокольцо, викивики. Такие «разночтения» могут встречаться и в ДНК.

3. Реализация проверки палиндрома на машине Тьюринга

тьюринг палиндром алгоритм

Построим машину Тьюринга, определяющую, является ли входное слово палиндромом. Алфавит машины: У = {0,1,>,?}.

Составим функцию переходов. Если лента пустая, то мы принимаем вход.

(q₀,?) > (q_yes,?,·). Если лента не пустая, то мы запоминаем в состоянии первый символ (q₂, если это 0 и q₃, если это 1), заменяем его на > и перемещаемся к концу ленты.

(q₀,0) > (q₂,>,>),

(q₀,1) > (q₃,>,>),

(q₂,0) > (q₂,0,>),

(q₂,1) > (q₂,1,>),

(q₃,0) > (q₃,0,>),

(q₃,1) > (q₃,1,>).

Как только встретился символ ?, мы возвращаемся на шаг назад и проверяем, какой символ предшествовал ему.

(q₂,?) > (q₄,?,<),

(q₃,?) > (q₅,?,<),

(q₄,1) > (q _no,1,·),

(q₅,0) > (q _no,0,·),

(q₄,>) > (q _yes,>,·),

(q₅,>) > (q _yes,>,·).

Если это подходящий символ, то мы возвращаемся к началу ленты и повторяем всё заново.

(q₄,0) > (q₆,0,<),

(q₅,1) > (q₆,1,<),

(q₆,0) > (q₆,0,<),

(q₆,1) > (q₆,1,<),

(q₆,>) > (q₀,>,>).

4. Время работы алгоритма

На входе длины n наша программа делает примерно 2 * ?(n²) шагов

Сложностью по времени на данном входе x называется число шагов, производимых до перехода в состояние q_yes.

Сложностью по времени называется функция T: N > N, где T(n) есть наибольшая сложность по времени для входов длиной n.

Мы используем принцип несжимаемости, известный в алгоритмической теории информации (колмогоровской сложности). Пусть имеется инъективное отображение f: {0,1}ⁿ > {0,1}^*. Тогда найдётся строка x ? {0,1}ⁿ, такая что |f(x)| ? n. Это легко видно из подсчёта: строк длиной n имеется 2ⁿ, а строк длиной ? n имеется 2⁰ +2¹ +···+2^n?1 =2ⁿ ? 1. То есть, при любом выбранном кодировании среди всех строк длиной n найдется несжимаемая строка, которая кодируется не менее чем n битами. Пусть машина Тьюринга M распознаёт язык палиндромов. В частности, она должна распознавать слова вида x0x^R, где x ? {0,1}ⁿ, а x^R - строка x, записанная в обратном порядке.

Рассмотрим «перегородки» между ячейками ленты и последовательности пересечения этих перегородок (последовательности, показывающие, в каком состоянии произошло очередное пересечение перегородки). Существует i-я перегородка, где n ? i ? 2ⁿ, такая что соответствующая последовательность пересечений S_i = (q₁,…, q_m) имеет длину m ? T(x)/n, где T(x) - время работы машины на входе x0x^R, и n = |x|. По числу i и последовательности S_i можно однозначно восстановить x.

Битовое представление S_i будет занимать не более C_M T(x)/n+2 log n, где log n требуется на хранение n и i. По этому описанию другая машина Тьюринга M` может сгенерировать x.

Теперь мы применяем принцип несжимаемости: сложность K(x) = |f(x)| строки x превосходит log n не более чем на константу C_{M`</sub>. Однако среди строк длиной n найдется несжимаемая строка x<sup>*</sup>, такая что K(x<sup>*</sup>) ? n. Таким образом, n ? K(x <sup>*</sup>) ? C<sub>M</sub> T(x<sup>*</sup>)/n + 2 log n + C<sub>M `}. Значит, T(x^*) = ?(n²).

Литература

1. Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман Глава 8. Введение в теорию машин Тьюринга // Введение в теорию автоматов, языков и вычислений

2. Теория сложности вычислений Д.М. ИцыксонРазмещено на Allbest.ru