1632
правки
Изменения
м
{{В разработке}}__TOC__
== Введение == '''Машина Тьюринга''' (англ. ''Turing machine'') — абстрактный вычислительмодель абстрактного вычислителя, предложенный предложенная британским математиком Аланом Тьюрингом в 1936 году . Эта модель позволила Тьюрингу доказать два утверждения. Первое — проблема останова неразрешима, т.е. не существует такой машины Тьюринга, которая способна определить, что другая произвольная машина Тьюринга на её ленте зациклится или прекратит работу. Второе — не существует такой машины Тьюринга, которая способна определить, что другая произвольная машина Тьюринга на её ленте когда-нибудь напечатает заданный символ. В этом же году был высказан тезис Чёрча-Тьюринга, который терминах теории рекурсии формулируется как точное описание интуитивного понятия вычислимости классом общерекурсивных функций. В этой формулировке часто упоминается как просто тезис Чёрча. В терминах вычислимости по Тьюрингу тезис гласит, что для формализации понятия алгоритмалюбой алгоритмически вычислимой функции существует вычисляющая её значения машина Тьюринга. В виду того, что классы частично вычислимых по Тьюрингу и частично рекурсивных функций совпадают, утверждение объединяют в единый тезис Чёрча — Тьюринга.
Формально машина Тьюринга определяется как кортеж из восьми элементов <tex>\langle \Sigma, \Pi, B, Q, Y, N, S, \delta \rangle</tex>, где== Источники информации ==* <tex>\Sigma<[http://www.cs.virginia.edu/~robins/tex> — алфавитTuring_Paper_1936.pdf Alan Turing {{---}} On computable numbers, из букв которого могут состоять входные словаwith an application to the Entscheidungsproblem.]* <tex>\Pi \supseteq \Sigma<[http:/tex> — символы/www.ccs.neu.edu/home/viola/classes/papers/HennieStearns66.pdf F. C. Hennie, которые могут быть записаны на ленту в процессе работы машиныR. E. Stearn {{---}} Two-tape simulation of multitape Turing machines.]* <tex>B \in \Pi \setminus \Sigma<[http://tex> — пробельный символ (от слова ''blank'')www.cs.princeton.edu/theory/index.php/Compbook/Draft Sanjeev Arora, Boaz Barak {{---}} Computational Complexity: A Modern Approach.]* <tex>Q<[http:/tex> — множество состояний управляющего автомата* <tex>Y \in Q</tex> — допускающее состояние автомата* <tex>N \in Q<citeseerx.ist.psu.edu/tex> — отвергающее состояние автомата* <tex>S \in Q<viewdoc/tex> — стартовое состояние автоматаsummary?doi=10.1.1.145.8958 Turlough Neary, Damien Woods {{---}} Four Small Universal Turing Machines.]* <tex>\delta [http: Q \times \Pi \to Q \times \Pi \times \//www.jflap.org/ JFLAP {{ \leftarrow---}} ПО для изучения формальных языков, \rightarrow, \downarrow \}</tex> — всюду определённая функция перехода автоматавключает в себя эмулятор одноленточных и многоленточных машин Тьюринга с визуальным редактором.]
Существуют различные вариации данного выше определения (например, без отвергающего состояния или с множеством допускающих состояний), которые не влияют на вычислительные способности машины Тьюринга.[[Категория: Теория формальных языков]][[Категория: Теория вычислимости]][[Категория: Вычислительные формализмы]]
rollbackEdits.php mass rollback
Неформально машина Тьюринга определяется как устройство, состоящее из двух частей:
* бесконечной одномерной ленты, разделённой на ячейки,
* головкойголовки, которая представляет из себя собой [[Детерминированные конечные автоматы|детерминированный конечный автомат]].
При запуске машины Тьюринга на ленте написано входное слово, причём на первом символе этого слова находится головка, а слева и справа от него записаны пустые символы. Каждый шаг головка может перезаписать символ под лентой и сместиться на одну ячейку, если автомат приходит в допускающее или отвергающее состояние, то работа машины Тьюринга завершается.
== Определение ==
=== Определение машины ===
{{Определение
|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=
Класс перечислимых языков совпадает с классом языков, перечислимых с помощью машин Тьюринга
}}
Иными словами, тезис говорит о том, что любой алгоритм можно запрограммировать на машине Тьюринга.
== Универсальная машина Тьюринга ==
Существует машина Тьюринга, которая принимает на вход закодированное описание произвольной машины и входную строку и эмулирует работу закодированной машины на заданном входном слове. Иными словами, [[Разрешимые (рекурсивные) языки#Пример неразрешимого множества|универсальный язык]] перечислим с помощью машины Тьюринга. Ссылки на явные конструкции универсальных машин Тьюринга приведены ниже.
== См. также ==
* [[Стековые машины, эквивалентность двухстековой машины МТ|Стековые машины]]
* [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ|Счётчиковые машины]]
* [[Линейный клеточный автомат, эквивалентность МТ|Клеточные автоматы]]
* [[Возможность порождения формальной грамматикой произвольного перечислимого языка|Произвольные формальные грамматики]]
* [[Лямбда-исчисление|Нетипизированное лямбда-исчисление]]
