304
правки
Изменения
м
bugfixes
Неформально машина Тьюринга определяется как устройство, состоящее из двух частей:
* бесконечной одномерной ленты, разделённой на ячейки,
* головкой, которая представляет собой [[Детерминированные конечные автоматы|детерминированный конечный автомат]].
При запуске машины Тьюринга на ленте написано входное слово, причём на первом символе этого слова находится головка, а слева и справа от него записаны пустые символы. Каждый шаг головка может перезаписать символ под лентой и сместиться на одну ячейку, если автомат приходит в допускающее или отвергающее состояние, то работа машины Тьюринга завершается.
Машину Тьюринга можно рассматривать как распознаватель слов языка. Пусть <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>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>.
=== Машина Тьюринга с полубесконечной лентой ===
== Ссылки ==
* Alan Turing, . On computable numbers, with an application to the Entscheidungsproblem [http://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf (ссылка)]
* 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 (ссылка)]
