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

2019-12-12T12:35:07Z

109.242.180.127: Отмена правки 71939, сделанной 84.47.152.2 (обсуждение)

__TOC__

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

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

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

== Определение ==
=== Определение машины ===
{{Определение
|definition=
Формально '''машина Тьюринга''' (англ. ''Turing machine'') определяется как кортеж из восьми элементов <tex>\langle \Sigma, \Pi, B, Q, Y, N, S, \delta \rangle</tex>, где
* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова,
* <tex>\Pi \supset \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> на ленту.
{{Определение
|id=conf
|definition=
Назовём '''конфигурацией''' машины Тьюринга тройку <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>v = \varepsilon</tex>).

В дальнейшем используются следующие обозначения: <tex>x, y, z \in \Pi</tex>, <tex>w, v \in \Pi^*</tex>
{{Определение
|definition=
Определим на конфигурациях отношение перехода <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</tex> приведена ниже:

{| border="0" cellspacing="5"
|-
|width="30"|
|width="100"| <tex>0</tex>
|width="100"| <tex>1</tex>
|width="100"| <tex>B</tex>
|-
| <tex>S</tex>
| <tex>\langle R, 1, \downarrow \rangle</tex>
| <tex>\langle S, 0, \rightarrow \rangle</tex>
| <tex>\langle R, B, \leftarrow \rangle</tex>
|-
| <tex>R</tex>
| <tex>\langle R, 0, \leftarrow \rangle</tex>
| <tex>\langle R, 1, \leftarrow \rangle</tex>
| <tex>\langle Y, B, \rightarrow \rangle</tex>
|}

=== Проверка того, является ли слово палиндромом ===
В качестве примера машины-распознавателя приведём машину, распознающую палиндромы над алфавитом <tex>\{0, 1\}</tex>. Алгоритм следующий:
* если строка на ленте — пустая, то перейти в допускающее состояние
* надо запомнить первый символ слова в состоянии автомата,
* стереть его,
* перейти в конец ленты:
** если оставшаяся строка на ленте — пустая, то перейти в допускающее состояние
** если последний символ совпадает с запомненным, стереть его, перейти в начало ленты и повторить с первого шага
** в случае несовпадения перейти в отвергающее состояние

Формально: <tex>\Sigma = \{0, 1\}</tex>, <tex>\Pi = \{0, 1, B\}</tex>, <tex>Q = \{S, F_0, F_1, B_0, B_1, R \}</tex>. Таблица функции <tex>\delta</tex> приведена ниже:
{| border="0" cellspacing="5"
|-
|width="30"|
|width="100"| <tex>0</tex>
|width="100"| <tex>1</tex>
|width="100"| <tex>B</tex>
|-
| <tex>S</tex>
| <tex>\langle F_0, B, \rightarrow \rangle</tex>
| <tex>\langle F_1, B, \rightarrow \rangle</tex>
| <tex>\langle Y, B, \downarrow \rangle</tex>
|-
| <tex>F_0</tex>
| <tex>\langle F_0, 0, \rightarrow \rangle</tex>
| <tex>\langle F_0, 1, \rightarrow \rangle</tex>
| <tex>\langle B_0, B, \leftarrow \rangle</tex>
|-
| <tex>F_1</tex>
| <tex>\langle F_1, 0, \rightarrow \rangle</tex>
| <tex>\langle F_1, 1, \rightarrow \rangle</tex>
| <tex>\langle B_1, B, \leftarrow \rangle</tex>
|-
| <tex>B_0</tex>
| <tex>\langle R, B, \leftarrow \rangle</tex>
| <tex>\langle N, 1, \downarrow \rangle</tex>
| <tex>\langle Y, B, \downarrow \rangle</tex>
|-
| <tex>B_1</tex>
| <tex>\langle N, 0, \downarrow \rangle</tex>
| <tex>\langle R, B, \leftarrow \rangle</tex>
| <tex>\langle Y, B, \downarrow \rangle</tex>
|-
| <tex>R</tex>
| <tex>\langle R, 0, \leftarrow \rangle</tex>
| <tex>\langle R, 1, \leftarrow \rangle</tex>
| <tex>\langle S, B, \rightarrow \rangle</tex>
|}

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

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

=== Машина Тьюринга с полубесконечной лентой ===
Заменив у машины Тьюринга бесконечную в обе стороны ленту на бесконечную в одну сторону, мы не теряем в вычислительной мощности. По произвольной машине Тьюринга строится двухдорожечная машина с полубесконечной лентой.
{{Теорема
|author=
|statement=Для любой машины Тьюринга существует эквивалентная машина Тьюринга, работающая на полубесконечной ленте.
|proof=Существует алгоритм, по которому для любой машины Тьюринга может быть построена эквивалентная машина Тьюринга с объявленным свойством. Сначала занумеруем ячейки рабочей ленты машины Тьюринга с ''бесконечной лентой'' следующим образом:

[[Файл:Mt1.png]]

Затем перенумеруем ячейки, и запишем символ <tex>c \in \Pi \setminus \Sigma, B</tex> в начало ленты, который будет означать границу рабочей зоны:

[[Файл:Mt2.png]]

Наконец, изменим машину Тьюринга, удвоив число её состояний, и изменим сдвиг головки так, чтобы в одной группе состояний работа машины была бы эквивалентна её работе в заштрихованной зоне, а в другой группе состояний машина работала бы так, как исходная машина работает в незаштрихованной зоне. Если при работе машины Тьюринга встретится символ <tex>c</tex>, значит головка достигла границы рабочей зоны:

[[Файл:Mt3.png]]

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

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

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

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

Аланом Тьюрингом было сформулировано следующее утверждение:
{{Утверждение
|about=Тезис Чёрча-Тьюринга
|statement=
Класс перечислимых языков совпадает с классом языков, перечислимых с помощью машин Тьюринга
}}
Иными словами, тезис говорит о том, что любой алгоритм можно запрограммировать на машине Тьюринга.

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

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

== См. также ==
* [[Стековые машины, эквивалентность двухстековой машины МТ|Стековые машины]]
* [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ|Счётчиковые машины]]
* [[Линейный клеточный автомат, эквивалентность МТ|Клеточные автоматы]]
* [[Возможность порождения формальной грамматикой произвольного перечислимого языка|Произвольные формальные грамматики]]
* [[Лямбда-исчисление|Нетипизированное лямбда-исчисление]]

== Источники информации ==
* [http://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf Alan Turing {{---}} On computable numbers, with an application to the Entscheidungsproblem.]
* [http://www.ccs.neu.edu/home/viola/classes/papers/HennieStearns66.pdf F. C. Hennie, R. E. Stearn {{---}} Two-tape simulation of multitape Turing machines.]
* [http://www.cs.princeton.edu/theory/index.php/Compbook/Draft Sanjeev Arora, Boaz Barak {{---}} Computational Complexity: A Modern Approach.]
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.145.8958 Turlough Neary, Damien Woods {{---}} Four Small Universal Turing Machines.]
* [http://www.jflap.org/ JFLAP {{---}} ПО для изучения формальных языков, включает в себя эмулятор одноленточных и многоленточных машин Тьюринга с визуальным редактором.]

[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
[[Категория: Вычислительные формализмы]]

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

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