Машина Тьюринга — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (убрал пункт "введение")
м (rollbackEdits.php mass rollback)
 
(не показаны 23 промежуточные версии 10 участников)
Строка 1: Строка 1:
{{В разработке}}
+
__TOC__
  
'''Машина Тьюринга''' (''Turing machine'') — абстрактный вычислитель, предложенный британским математиком Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.
+
'''Машина Тьюринга''' (англ. ''Turing machine'') — модель абстрактного вычислителя, предложенная британским математиком Аланом Тьюрингом в 1936 году. Эта модель позволила Тьюрингу доказать два утверждения. Первое — проблема останова неразрешима, т.е. не существует такой машины Тьюринга, которая способна определить, что другая произвольная машина Тьюринга на её ленте зациклится или прекратит работу. Второе — не существует такой машины Тьюринга, которая способна определить, что другая произвольная машина Тьюринга на её ленте когда-нибудь напечатает заданный символ. В этом же году был высказан тезис Чёрча-Тьюринга, который терминах теории рекурсии формулируется как точное описание интуитивного понятия вычислимости классом общерекурсивных функций. В этой формулировке часто упоминается как просто тезис Чёрча. В терминах вычислимости по Тьюрингу тезис гласит, что для любой алгоритмически вычислимой функции существует вычисляющая её значения машина Тьюринга. В виду того, что классы частично вычислимых по Тьюрингу и частично рекурсивных функций совпадают, утверждение объединяют в единый тезис Чёрча — Тьюринга.
  
 
Неформально машина Тьюринга определяется как устройство, состоящее из двух частей:
 
Неформально машина Тьюринга определяется как устройство, состоящее из двух частей:
 
* бесконечной одномерной ленты, разделённой на ячейки,
 
* бесконечной одномерной ленты, разделённой на ячейки,
* головкой, которая представляет собой детерминированный конечный автомат.
+
* головки, которая представляет собой [[Детерминированные конечные автоматы|детерминированный конечный автомат]].
  
 
При запуске машины Тьюринга на ленте написано входное слово, причём на первом символе этого слова находится головка, а слева и справа от него записаны пустые символы. Каждый шаг головка может перезаписать символ под лентой и сместиться на одну ячейку, если автомат приходит в допускающее или отвергающее состояние, то работа машины Тьюринга завершается.
 
При запуске машины Тьюринга на ленте написано входное слово, причём на первом символе этого слова находится головка, а слева и справа от него записаны пустые символы. Каждый шаг головка может перезаписать символ под лентой и сместиться на одну ячейку, если автомат приходит в допускающее или отвергающее состояние, то работа машины Тьюринга завершается.
Строка 13: Строка 13:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Формально машина Тьюринга определяется как кортеж из восьми элементов <tex>\langle \Sigma, \Pi, B, Q, Y, N, S, \delta \rangle</tex>, где
+
Формально '''машина Тьюринга''' (англ. ''Turing machine'') определяется как кортеж из восьми элементов <tex>\langle \Sigma, \Pi, B, Q, Y, N, S, \delta \rangle</tex>, где
* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова
+
* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова,
* <tex>\Pi \supseteq \Sigma</tex> — символы, которые могут быть записаны на ленту в процессе работы машины
+
* <tex>\Pi \supset \Sigma</tex> — символы, которые могут быть записаны на ленту в процессе работы машины,
* <tex>B \in \Pi \setminus \Sigma</tex> ­— пробельный символ (от слова ''blank'')
+
* <tex>B \in \Pi \setminus \Sigma</tex> ­— пробельный символ (от слова ''blank''),
* <tex>Q</tex> — множество состояний управляющего автомата
+
* <tex>Q</tex> — множество состояний управляющего автомата,
* <tex>Y \in Q</tex> — допускающее состояние автомата
+
* <tex>Y \in Q</tex> — допускающее состояние автомата,
* <tex>N \in Q</tex> — отвергающее состояние автомата
+
* <tex>N \in Q</tex> — отвергающее состояние автомата,
* <tex>S \in Q</tex> — стартовое состояние автомата
+
* <tex>S \in Q</tex> — стартовое состояние автомата,
* <tex>\delta : Q \times \Pi \to Q \times \Pi \times \{ \leftarrow, \rightarrow, \downarrow \}</tex> — всюду определённая функция перехода автомата
+
* <tex>\delta : Q \times \Pi \to Q \times \Pi \times \{ \leftarrow, \rightarrow, \downarrow \}</tex> — всюду определённая функция перехода автомата.
 
}}
 
}}
 
Отметим, что существуют различные вариации данного выше определения (например, без отвергающего состояния или с множеством допускающих состояний), которые не влияют на вычислительные способности машины Тьюринга.
 
Отметим, что существуют различные вариации данного выше определения (например, без отвергающего состояния или с множеством допускающих состояний), которые не влияют на вычислительные способности машины Тьюринга.
Строка 28: Строка 28:
 
Кроме формального определения самой машины требуется также формально описать процесс её работы. В определении для простоты будем предполагать, что головка в процессе работы не записывает на ленту символ <tex>B</tex>. Это не ограничивает вычислительной мощности машин Тьюринга, поскольку для каждой машины можно сопоставить аналогичную ей, но не пищущую <tex>B</tex> на ленту.
 
Кроме формального определения самой машины требуется также формально описать процесс её работы. В определении для простоты будем предполагать, что головка в процессе работы не записывает на ленту символ <tex>B</tex>. Это не ограничивает вычислительной мощности машин Тьюринга, поскольку для каждой машины можно сопоставить аналогичную ей, но не пищущую <tex>B</tex> на ленту.
 
{{Определение
 
{{Определение
 +
|id=conf
 
|definition=
 
|definition=
Назовём '''конфигурацией''' машины Тьюринга тройку <tex>\langle w, q, v \rangle</tex>, где <tex>q \in Q</tex> — текущее состояние автомата, а <tex>w, v \in (\Pi \setminus \{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>v</tex> (или <tex>B</tex>, если <tex>v = \varepsilon</tex>).
  
 
В дальнейшем используются следующие обозначения: <tex>x, y, z \in \Pi</tex>, <tex>w, v \in \Pi^*</tex>
 
В дальнейшем используются следующие обозначения: <tex>x, y, z \in \Pi</tex>, <tex>w, v \in \Pi^*</tex>
Строка 37: Строка 40:
 
|definition=
 
|definition=
 
Определим на конфигурациях отношение перехода <tex>\langle w_1, q_1, v_1 \rangle \vdash \langle w_2, q_2, v_2 \rangle</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, \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, \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, 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, \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, \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>\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>C</tex> существует не более одной конфигурации <tex>C'</tex>, для которой <tex>C \vdash C'</tex>.
  
Для машины Тьюринга, которая пишет символ <tex>B</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>\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>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> можно интерпретировать как аварийное завершение программы (например, при некорретном входе).
  
 
Примеры машин-распознавателей и машин-преобразователей будут даны ниже.
 
Примеры машин-распознавателей и машин-преобразователей будут даны ниже.
Строка 138: Строка 141:
  
 
=== Многодорожечная машина Тьюринга ===
 
=== Многодорожечная машина Тьюринга ===
Машиной Тьюринга с <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>.
+
Машиной Тьюринга с <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>.
  
 
=== Машина Тьюринга с полубесконечной лентой ===
 
=== Машина Тьюринга с полубесконечной лентой ===
Заменив у машины Тьюринга бесконечную в обе стороны ленту на бесконечную в одну сторону, мы не теряем в вычислительной мощности. По произвольной машине Тьюринга строится двухдорожечная машина с полубесконечной лентой следующим образом: в первой ячейке записывается символ <tex>\mathbb T</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>\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>n</tex> дорожками эмулируется многодорожечной машиной с <tex>2n</tex> дорожками следующим образом: каждая нечётная дорожка соответствует ленте исходной машины, а на каждой чётной дорожке отмечены специальным символом <tex>*</tex> позиция головки на ленте выше (считаем, что ленты нумеруются сверху вниз).
  
 
Каждый шаг исходной машины эмулируется конечной последовательностью шагов построенной машины следующим образом: исходно головка находится в позиции самой левой отметки и идёт вправо до самой правой отметки, запоминая прочитанные около символов <tex>*</tex> символы в состоянии. Пройдя до самой правой отметки, головка возвращается влево, совершая необходимые действия (переписывая символы около отметок и передвигая сами отметки). После такого прохода головка переходит в следующее состояние, завершая эмуляцию шага.
 
Каждый шаг исходной машины эмулируется конечной последовательностью шагов построенной машины следующим образом: исходно головка находится в позиции самой левой отметки и идёт вправо до самой правой отметки, запоминая прочитанные около символов <tex>*</tex> символы в состоянии. Пройдя до самой правой отметки, головка возвращается влево, совершая необходимые действия (переписывая символы около отметок и передвигая сами отметки). После такого прохода головка переходит в следующее состояние, завершая эмуляцию шага.
  
=== Другие эквивалентные вычислительные формализмы ===
+
Аланом Тьюрингом было сформулировано следующее утверждение:
Существуют также другие формализации понятия алгоритма, которые по вычислительным возможностям эквивалентны машинам Тьюринга:
+
{{Утверждение
* [[Стековые машины, эквивалентность двухстековой машины МТ|стековые машины]]
+
|about=Тезис Чёрча-Тьюринга
* [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ|счётчиковые машины]]
+
|statement=
* [[Линейный клеточный автомат, эквивалентность МТ|клеточные автоматы]]
+
Класс перечислимых языков совпадает с классом языков, перечислимых с помощью машин Тьюринга
* [[Возможность порождения формальной грамматикой произвольного перечислимого языка|произвольные формальные грамматики]]
+
}}
* [[Лямбда-исчисление|нетипизированное лямбда-исчисление]]
+
Иными словами, тезис говорит о том, что любой алгоритм можно запрограммировать на машине Тьюринга.
  
 
== Универсальная машина Тьюринга ==
 
== Универсальная машина Тьюринга ==
Строка 162: Строка 182:
 
Существует машина Тьюринга, которая принимает на вход закодированное описание произвольной машины и входную строку и эмулирует работу закодированной машины на заданном входном слове. Иными словами, [[Разрешимые (рекурсивные) языки#Пример неразрешимого множества|универсальный язык]] перечислим с помощью машины Тьюринга. Ссылки на явные конструкции универсальных машин Тьюринга приведены ниже.
 
Существует машина Тьюринга, которая принимает на вход закодированное описание произвольной машины и входную строку и эмулирует работу закодированной машины на заданном входном слове. Иными словами, [[Разрешимые (рекурсивные) языки#Пример неразрешимого множества|универсальный язык]] перечислим с помощью машины Тьюринга. Ссылки на явные конструкции универсальных машин Тьюринга приведены ниже.
  
== Ссылки ==
+
== См. также ==
* 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 [http://www.ccs.neu.edu/home/viola/classes/papers/HennieStearns66.pdf (ссылка)]
+
* [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ|Счётчиковые машины]]
* Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach, Chapter 1 [http://www.cs.princeton.edu/theory/index.php/Compbook/Draft (ссылка)]
+
* [[Линейный клеточный автомат, эквивалентность МТ|Клеточные автоматы]]
 +
* [[Возможность порождения формальной грамматикой произвольного перечислимого языка|Произвольные формальные грамматики]]
 +
* [[Лямбда-исчисление|Нетипизированное лямбда-исчисление]]
 +
 
 +
== Источники информации ==
 +
* [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 {{---}} ПО для изучения формальных языков, включает в себя эмулятор одноленточных и многоленточных машин Тьюринга с визуальным редактором.]
 +
 
 +
[[Категория: Теория формальных языков]]
 +
[[Категория: Теория вычислимости]]
 +
[[Категория: Вычислительные формализмы]]

Текущая версия на 19:15, 4 сентября 2022

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

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

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

Определение

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

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

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

Mt1.png

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

Mt2.png

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

Mt3.png

Начальное состояние новой машины Тьюринга устанавливается в одной или другой зоне в зависимости от того, в какой части исходной ленты располагалась головка считывания-записи в исходной конфигурации.
[math]\triangleleft[/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] символы в состоянии. Пройдя до самой правой отметки, головка возвращается влево, совершая необходимые действия (переписывая символы около отметок и передвигая сами отметки). После такого прохода головка переходит в следующее состояние, завершая эмуляцию шага.

Аланом Тьюрингом было сформулировано следующее утверждение:

Утверждение (Тезис Чёрча-Тьюринга):
Класс перечислимых языков совпадает с классом языков, перечислимых с помощью машин Тьюринга

Иными словами, тезис говорит о том, что любой алгоритм можно запрограммировать на машине Тьюринга.

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

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

См. также

Источники информации