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

2012-12-06T13:23:39Z

94.25.229.30: добавлен пример

{{В разработке}}

== Введение ==

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

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

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

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

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

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

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

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

Определим на конфигурациях отношение перехода <tex>\langle w_1, q_1, v_1 \rangle \vdash \langle w_2, q_2, v_2 \rangle</tex>:
* если <tex>\delta(q, x) = \langle p, y, \leftarrow \rangle</tex>, то <tex>\langle wz, q, xv \rangle \vdash \langle w, p, zyv \rangle</tex>
* если <tex>\delta(q, x) = \langle p, y, \rightarrow \rangle</tex>, то <tex>\langle w, q, xv \rangle \vdash \langle wy, p, v \rangle</tex>
* если <tex>\delta(q, x) = \langle p, y, \downarrow \rangle</tex>, то <tex>\langle w, q, xv \rangle \vdash \langle w, p, yv \rangle</tex>

Особо следует рассмотреть случай переходов по пробельному символу:
* если <tex>\delta(q, B) = \langle p, y, \leftarrow \rangle</tex>, то <tex>\langle wz, q, \varepsilon \rangle \vdash \langle w, p, zy \rangle</tex>
* если <tex>\delta(q, B) = \langle p, y, \rightarrow \rangle</tex>, то <tex>\langle w, q, \varepsilon \rangle \vdash \langle wy, p, \varepsilon \rangle</tex>
* если <tex>\delta(q, B) = \langle p, y, \downarrow \rangle</tex>, то <tex>\langle w, q, \varepsilon \rangle \vdash \langle w, p, y \rangle</tex>

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

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

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

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

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

== Примеры машин Тьюринга ==
Для начала приведём пример машины-преобразователя, которая прибавляет единицу к числу, записанному на ленте в двоичной записи от младшего бита к старшему. Алгоритм следующий:
* в стартовом состоянии головка идёт вправо от младшего бита к старшему, заменяя все единицы на нули,
* встретив нуль или пробельный символ головка записывает единицу, после чего переходит в состояние <tex>R</tex>,
* в состоянии <tex>R</tex> головка идёт влево от старшего бита к младшему, не изменяя символы 0 и 1 на ленте,
* встретив в состоянии <tex>R</tex> пробельный символ, головка перемещается на один символ вправо и переходит в состояние <tex>Y</tex>, завершая работу.

Следующее определение формализует данный алгоритм:
* <tex>\Sigma = \{0, 1 \}</tex>, <tex>\Pi = \{0, 1, B\}</tex>
* <tex>Q = \{S, R, Y, N \}</tex>
** <tex>\delta(S, 1) = \langle S, 0, \rightarrow \rangle</tex>
** <tex>\delta(S, 0) = \langle R, 1, \downarrow \rangle</tex>
** <tex>\delta(S, B) = \langle R, 1, \downarrow \rangle</tex>
** <tex>\delta(R, 0) = \langle R, 0, \leftarrow \rangle</tex>
** <tex>\delta(R, 1) = \langle R, 1, \leftarrow \rangle</tex>
** <tex>\delta(R, B) = \langle Y, B, \rightarrow \rangle</tex>

Викиконспекты - Вклад участника [ru]

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