Изменения

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

* головкойголовки, которая представляет из себя собой [[Детерминированные конечные автоматы|детерминированный конечный автомат]].

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

Кроме формального определения самой машины требуется также формально описать процесс её работы. В определении для простоты будем предполагать, что головка в процессе работы не записывает на ленту символ <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>w v = \varepsilon</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>CB</tex> существует не более одной на ленту также можно дать аналогичное формальное определение. Оно будет отличаться тем, что символы в строчках конфигурации <tex>C'</tex>могут содержать пробелы, и для которой <tex>C \vdash C'</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 {{---}} ПО для изучения формальных языков, включает в себя эмулятор одноленточных и многоленточных машин Тьюринга с визуальным редактором.]