26
правок
Изменения
Нет описания правки
'''Машина Тьюринга''' (англ. ''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> — всюду определённая функция перехода автомата
}}
|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>,
Особо следует рассмотреть случай переходов по пробельному символу:
|proof=Существует алгоритм, по которому для любой машины Тьюринга может быть построена эквивалентная машина Тьюринга с объявленным свойством. Сначала занумеруем ячейки рабочей ленты машины Тьюринга с ''бесконечной лентой'' следующим образом:
[[Файл:Mt1.jpgpng]]
Затем перенумеруем ячейки, и запишем символ <tex>c \in \Pi \setminus \Sigma, B</tex> в начало ленты, который будет означать границу рабочей зоны:
[[Файл:Mt2.jpgpng]]
Наконец, изменим машину Тьюринга, удвоив число её состояний, и изменим сдвиг головки так, чтобы в одной группе состояний работа машины была бы эквивалентна её работе в заштрихованной зоне, а в другой группе состояний машина работала бы так, как исходная машина работает в незаштрихованной зоне. Если при работе машины Тьюринга встретится символ <tex>c</tex>, значит головка достигла границы рабочей зоны:
Каждый шаг исходной машины эмулируется конечной последовательностью шагов построенной машины следующим образом: исходно головка находится в позиции самой левой отметки и идёт вправо до самой правой отметки, запоминая прочитанные около символов <tex>*</tex> символы в состоянии. Пройдя до самой правой отметки, головка возвращается влево, совершая необходимые действия (переписывая символы около отметок и передвигая сами отметки). После такого прохода головка переходит в следующее состояние, завершая эмуляцию шага.
Аланом Тьюрингом было сформулировано следующее утверждение:
Существует машина Тьюринга, которая принимает на вход закодированное описание произвольной машины и входную строку и эмулирует работу закодированной машины на заданном входном слове. Иными словами, [[Разрешимые (рекурсивные) языки#Пример неразрешимого множества|универсальный язык]] перечислим с помощью машины Тьюринга. Ссылки на явные конструкции универсальных машин Тьюринга приведены ниже.
== См. также ==
* [[Стековые машины, эквивалентность двухстековой машины МТ|стековые машины]]
* [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ|счётчиковые машины]]
* [[Линейный клеточный автомат, эквивалентность МТ|клеточные автоматы]]
* [[Возможность порождения формальной грамматикой произвольного перечислимого языка|произвольные формальные грамматики]]
* [[Лямбда-исчисление|нетипизированное лямбда-исчисление]]
== Источники информации ==
[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
[[Категория: Вычислительные формализмы]]
