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

Эта статья находится в разработке!

Введение

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

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

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

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

Определение

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

Формально машина Тьюринга определяется как кортеж из восьми элементов [math]\langle \Sigma, \Pi, B, Q, Y, N, S, \delta \rangle[/math], где

• [math]\Sigma[/math] — алфавит, из букв которого могут состоять входные слова
• [math]\Pi \supseteq \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]w = \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]\mathbb T[/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 and R. E. Stearns. Two-tape simulation of multitape Turing machines (1)
• Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach (1)