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

Машина Тьюринга (англ. Turing machine) — модель абстрактного вычислителя, предложенная британским математиком Аланом Тьюрингом в 1936 году. Эта модель позволила Тьюрингу доказать два утверждения. Первое - проблема останова неразрешима, т.е. не существует такой машины Тьюринга, которая способна определить, что другая произвольная машина Тьюринга на её ленте зациклится или прекратит работу. Второе - не существует такой машины Тьюринга, которая способна определить, что другая произвольная машина Тьюринга на её ленте когда-нибудь напечатает заданный символ. В этом же году был высказан тезис Чёрча-Тьюринга, который терминах теории рекурсии формулируется как точное описание интуитивного понятия вычислимости классом общерекурсивных функций. В этой формулировке часто упоминается как просто тезис Чёрча. В терминах вычислимости по Тьюрингу тезис гласит, что для любой алгоритмически вычислимой функции существует вычисляющая её значения машина Тьюринга. В виду того, что классы частично вычислимых по Тьюрингу и частично рекурсивных функций совпадают, утверждение объединяют в единый тезис Чёрча — Тьюринга.

Неформально машина Тьюринга определяется как устройство, состоящее из двух частей:

• бесконечной одномерной ленты, разделённой на ячейки,
• головки, которая представляет собой детерминированный конечный автомат.

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

Определение

Определение машины

Определение:

Формально машина Тьюринга определяется как кортеж из восьми элементов [math]\langle \Sigma, \Pi, B, Q, Y, N, S, \delta \rangle[/math], где [math]\Sigma[/math] — алфавит, из букв которого могут состоять входные слова [math]\Pi \supset \Sigma[/math] — символы, которые могут быть записаны на ленту в процессе работы машины [math]B \in \Pi \setminus \Sigma[/math] ­— пробельный символ (от слова blank) [math]Q[/math] — множество состояний управляющего автомата [math]Y \in Q[/math] — допускающее состояние автомата [math]N \in Q[/math] — отвергающее состояние автомата [math]S \in Q[/math] — стартовое состояние автомата [math]\delta : Q \times \Pi \to Q \times \Pi \times \{ \leftarrow, \rightarrow, \downarrow \}[/math] — всюду определённая функция перехода автомата

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

Определение процесса работы

Кроме формального определения самой машины требуется также формально описать процесс её работы. В определении для простоты будем предполагать, что головка в процессе работы не записывает на ленту символ [math]B[/math]. Это не ограничивает вычислительной мощности машин Тьюринга, поскольку для каждой машины можно сопоставить аналогичную ей, но не пищущую [math]B[/math] на ленту.

Определение:

Назовём конфигурацией машины Тьюринга тройку [math]\langle w, q, v \rangle[/math], где [math]q \in Q[/math] — текущее состояние автомата, а [math]w, v \in (\Pi \setminus \{B\})^*[/math] — строки слева и справа от головки до первого пробельного символа соответственно.

В данной записи головка находится над ячейкой, на которой написана первая буква [math]v[/math] (или [math]B[/math], если [math]v = \varepsilon[/math]).

В дальнейшем используются следующие обозначения: [math]x, y, z \in \Pi[/math], [math]w, v \in \Pi^*[/math]

Определение:

Определим на конфигурациях отношение перехода [math]\langle w_1, q_1, v_1 \rangle \vdash \langle w_2, q_2, v_2 \rangle[/math]: если [math]\delta(q, x) = \langle p, y, \leftarrow \rangle[/math], то [math]\langle wz, q, xv \rangle \vdash \langle w, p, zyv \rangle[/math] если [math]\delta(q, x) = \langle p, y, \rightarrow \rangle[/math], то [math]\langle w, q, xv \rangle \vdash \langle wy, p, v \rangle[/math] если [math]\delta(q, x) = \langle p, y, \downarrow \rangle[/math], то [math]\langle w, q, xv \rangle \vdash \langle w, p, yv \rangle[/math] Особо следует рассмотреть случай переходов по пробельному символу: если [math]\delta(q, B) = \langle p, y, \leftarrow \rangle[/math], то [math]\langle wz, q, \varepsilon \rangle \vdash \langle w, p, zy \rangle[/math] если [math]\delta(q, B) = \langle p, y, \rightarrow \rangle[/math], то [math]\langle w, q, \varepsilon \rangle \vdash \langle wy, p, \varepsilon \rangle[/math] если [math]\delta(q, B) = \langle p, y, \downarrow \rangle[/math], то [math]\langle w, q, \varepsilon \rangle \vdash \langle w, p, y \rangle[/math]

Очевидно, что определённое отношение является функциональным: для каждой конфигурации [math]C[/math] существует не более одной конфигурации [math]C'[/math], для которой [math]C \vdash C'[/math].

Для машины Тьюринга, которая пишет символ [math]B[/math] на ленту также можно дать аналогичное формальное определение. Оно будет отличаться тем, что символы в строчках конфигурации могут содержать пробелы, и для того, чтобы эти строчки имекли конечную длину, нужно аккуратно учесть наличие пробелов при записи правил перехода.

Результат работы

Машину Тьюринга можно рассматривать как распознаватель слов формального языка. Пусть [math]M[/math] — машина Тьюринга, распознаваемый ей язык определяется как [math]\mathcal L(M) = \{ x \in \Sigma^* \mid \exists y, z \in \Pi^*: \langle \varepsilon, S, x \rangle \vdash^* \langle y, Y, z \rangle \}[/math].

Также можно рассматривать машины Тьюринга как преобразователь входных данных в выходные. Машина [math]M[/math] задаёт вычислимую функцию [math]f[/math], причём [math]f(x) = y \Leftrightarrow \exists z \in \Pi^* : \langle \varepsilon, S, x \rangle \vdash^* \langle z, Y, y \rangle[/math]. Переход автомата в состояние [math]N[/math] можно интерпретировать как аварийное завершение программы (например, при некорретном входе).

Примеры машин-распознавателей и машин-преобразователей будут даны ниже.

Примеры машин Тьюринга

Прибавление единицы

Для начала приведём пример машины-преобразователя, которая прибавляет единицу к числу, записанному на ленте в двоичной записи от младшего бита к старшему. Алгоритм следующий:

• в стартовом состоянии головка идёт вправо от младшего бита к старшему, заменяя все единицы на нули,
• встретив нуль или пробельный символ головка записывает единицу, после чего переходит в состояние [math]R[/math],
• в состоянии [math]R[/math] головка идёт влево от старшего бита к младшему, не изменяя символы 0 и 1 на ленте,
• встретив в состоянии [math]R[/math] пробельный символ, головка перемещается на один символ вправо и переходит в состояние [math]Y[/math], завершая работу.

Формально: [math]\Sigma = \{0, 1 \}[/math], [math]\Pi = \{0, 1, B\}[/math], [math]Q = \{S, R, Y, N \}[/math]. Таблица функции [math]\delta[/math] приведена ниже:

	[math]0[/math]	[math]1[/math]	[math]B[/math]
[math]S[/math]	[math]\langle R, 1, \downarrow \rangle[/math]	[math]\langle S, 0, \rightarrow \rangle[/math]	[math]\langle R, B, \leftarrow \rangle[/math]
[math]R[/math]	[math]\langle R, 0, \leftarrow \rangle[/math]	[math]\langle R, 1, \leftarrow \rangle[/math]	[math]\langle Y, B, \rightarrow \rangle[/math]

Проверка того, является ли слово палиндромом

В качестве примера машины-распознавателя приведём машину, распознающую палиндромы над алфавитом [math]\{0, 1\}[/math]. Алгоритм следующий:

• если строка на ленте — пустая, то перейти в допускающее состояние
• надо запомнить первый символ слова в состоянии автомата,
• стереть его,
• перейти в конец ленты:
  • если оставшаяся строка на ленте — пустая, то перейти в допускающее состояние
  • если последний символ совпадает с запомненным, стереть его, перейти в начало ленты и повторить с первого шага
  • в случае несовпадения перейти в отвергающее состояние

Формально: [math]\Sigma = \{0, 1\}[/math], [math]\Pi = \{0, 1, B\}[/math], [math]Q = \{S, F_0, F_1, B_0, B_1, R \}[/math]. Таблица функции [math]\delta[/math] приведена ниже:

	[math]0[/math]	[math]1[/math]	[math]B[/math]
[math]S[/math]	[math]\langle F_0, B, \rightarrow \rangle[/math]	[math]\langle F_1, B, \rightarrow \rangle[/math]	[math]\langle Y, B, \downarrow \rangle[/math]
[math]F_0[/math]	[math]\langle F_0, 0, \rightarrow \rangle[/math]	[math]\langle F_0, 1, \rightarrow \rangle[/math]	[math]\langle B_0, B, \leftarrow \rangle[/math]
[math]F_1[/math]	[math]\langle F_1, 0, \rightarrow \rangle[/math]	[math]\langle F_1, 1, \rightarrow \rangle[/math]	[math]\langle B_1, B, \leftarrow \rangle[/math]
[math]B_0[/math]	[math]\langle R, B, \leftarrow \rangle[/math]	[math]\langle N, 1, \downarrow \rangle[/math]	[math]\langle Y, B, \downarrow \rangle[/math]
[math]B_1[/math]	[math]\langle N, 0, \downarrow \rangle[/math]	[math]\langle R, B, \leftarrow \rangle[/math]	[math]\langle Y, B, \downarrow \rangle[/math]
[math]R[/math]	[math]\langle R, 0, \leftarrow \rangle[/math]	[math]\langle R, 1, \leftarrow \rangle[/math]	[math]\langle S, B, \rightarrow \rangle[/math]

Варианты машины Тьюринга

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

Многодорожечная машина Тьюринга

Машиной Тьюринга с [math]n[/math] дорожками называется вычислитель, аналогичный машине Тьюринга, лишь с тем отличием, что лента состоит из [math]n[/math] дорожек, на каждой из которых записаны символы ленточного алфавита. У многодорожечной машины одна головка, которая за один шаг переходит в одном направлении на всех дорожках одновременно. Соответственно, функция перехода имеет тип [math]\delta : Q \times \Pi^n \to Q \times \Pi^n \times \{\leftarrow, \rightarrow, \downarrow\}[/math]. Многодорожечная машина Тьюринга тривиально эквивалентна обычной с ленточным алфавитом [math]\Pi' = \Pi^n[/math].

Машина Тьюринга с полубесконечной лентой

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

Теорема:

Для любой машины Тьюринга существует эквивалентная машина Тьюринга, работающая на полубесконечной ленте.

Доказательство:

[math]\triangleright[/math]

Существует алгоритм, по которому для любой машины Тьюринга может быть построена эквивалентная машина Тьюринга с объявленным свойством. Сначала занумеруем ячейки рабочей ленты машины Тьюринга с бесконечной лентой следующим образом: Затем перенумеруем ячейки, и запишем символ [math]c \in \Pi \setminus \Sigma, B[/math] в начало ленты, который будет означать границу рабочей зоны: Наконец, изменим машину Тьюринга, удвоив число её состояний, и изменим сдвиг головки так, чтобы в одной группе состояний работа машины была бы эквивалентна её работе в заштрихованной зоне, а в другой группе состояний машина работала бы так, как исходная машина работает в незаштрихованной зоне. Если при работе машины Тьюринга встретится символ [math]c[/math], значит головка достигла границы рабочей зоны: Начальное состояние новой машины Тьюринга устанавливается в одной или другой зоне в зависимости от того, в какой части исходной ленты располагалась головка считывания-записи в исходной конфигурации.

[math]\triangleleft[/math]

Многоленточная машина Тьюринга

В отличие от многодорожечной машины Тьюринга, ленты не зависят друг от друга и головки во время одного шага могу перемещаться по-разному. То есть, функция перехода теперь имеет тип [math]\delta : Q \times \Pi^n \to Q \times \Pi^n \times \{\leftarrow, \rightarrow, \downarrow\}^n[/math].

Многоленточная машина с [math]n[/math] дорожками эмулируется многодорожечной машиной с [math]2n[/math] дорожками следующим образом: каждая нечётная дорожка соответствует ленте исходной машины, а на каждой чётной дорожке отмечены специальным символом [math]*[/math] позиция головки на ленте выше (считаем, что ленты нумеруются сверху вниз).

Каждый шаг исходной машины эмулируется конечной последовательностью шагов построенной машины следующим образом: исходно головка находится в позиции самой левой отметки и идёт вправо до самой правой отметки, запоминая прочитанные около символов [math]*[/math] символы в состоянии. Пройдя до самой правой отметки, головка возвращается влево, совершая необходимые действия (переписывая символы около отметок и передвигая сами отметки). После такого прохода головка переходит в следующее состояние, завершая эмуляцию шага.

Другие эквивалентные вычислительные формализмы

Существуют также другие формализации понятия алгоритма, которые по вычислительным возможностям эквивалентны машинам Тьюринга:

• стековые машины
• счётчиковые машины
• клеточные автоматы
• произвольные формальные грамматики
• нетипизированное лямбда-исчисление

Аланом Тьюрингом было сформулировано следующее утверждение:

Утверждение (Тезис Чёрча-Тьюринга):

Класс перечислимых языков совпадает с классом языков, перечислимых с помощью машин Тьюринга

Иными словами, тезис говорит о том, что любой алгоритм можно запрограммировать на машине Тьюринга.

Универсальная машина Тьюринга

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

Источники информации

• Alan Turing — On computable numbers, with an application to the Entscheidungsproblem.
• F. C. Hennie, R. E. Stearn — Two-tape simulation of multitape Turing machines.
• Sanjeev Arora, Boaz Barak — Computational Complexity: A Modern Approach.
• Turlough Neary, Damien Woods — Four Small Universal Turing Machines.
• JFLAP — ПО для изучения формальных языков, включает в себя эмулятор одноленточных и многоленточных машин Тьюринга с визуальным редактором.