Изменения

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

Формально '''машина Тьюринга ''' определяется как кортеж из восьми элементов <tex>\langle \Sigma, \Pi, B, Q, Y, N, S, \delta \rangle</tex>, где

Заменив у машины Тьюринга бесконечную в обе стороны ленту на бесконечную в одну сторону, мы не теряем в вычислительной мощности. По произвольной машине Тьюринга строится двухдорожечная машина с полубесконечной лентой .{{Теорема|author=|statement=Для любой машины Тьюринга существует эквивалентная машина Тьюринга, работающая на полубесконечной ленте.|proof=Существует алгоритм, по которому для любой машины Тьюринга может быть построена эквивалентная машина Тьюринга с объявленным свойством. Сначала занумеруем ячейки рабочей ленты машины Тьюринга с ''бесконечной лентой'' следующим образом: в первой ячейке записывается  [[Файл:Mt1.jpg]] Затем перенумеруем ячейки, и запишем символ <tex>c \in \mathbb TPi \setminus \Sigma, B</tex> (подразумеваетсяв начало ленты, что он не является ленточным символом исходной машины)который будет означать границу рабочей зоны: [[Файл:Mt2.jpg]] Наконец, изменим машину Тьюринга, который сигнализирует о томудвоив число её состояний, что нужно перейти с дорожки на дорожку и двигаться изменим сдвиг головки так, чтобы в обратном направлении. Это реализуется с помощью создания копий всех одной группе состояний работа машины была бы эквивалентна её работе в заштрихованной зоне, а в другой группе состояний исходного автоматамашина работала бы так, как исходная машина работает в незаштрихованной зоне. Если при этом правила для копии используют для чтения и работе машины Тьюринга встретится символ <tex>c</tex>, значит головка достигла границы рабочей зоны: [[Файл:Mt3.jpg]] Начальное состояние новой машины Тьюринга устанавливается в одной или другой зоне в зависимости от того, в какой части исходной ленты располагалась головка считывания-записи вторую ленту и перемещают головку в противоположном направленииисходной конфигурации.}}

В отличие от многодорожечной машины Тьюринга, ленты не зависят друг от друга и головки во время одного шага могу перемещаться по-разному. То есть, функция перехода теперь имеет тип <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> позиция головки на ленте выше (считаем, что ленты нумеруются сверху вниз).

== Ссылки Источники информации ==* Alan Turing. [http://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf Alan Turing {{---}} On computable numbers, with an application to the Entscheidungsproblem.]* F. C. Hennie, R. E. Stearns. [http://www.ccs.neu.edu/home/viola/classes/papers/HennieStearns66.pdf F. C. Hennie, R. E. Stearn {{---}} Two-tape simulation of multitape Turing machines.]* Sanjeev Arora, Boaz Barak. [http://www.cs.princeton.edu/theory/index.php/Compbook/Draft Sanjeev Arora, Boaz Barak {{---}} Computational Complexity: A Modern Approach.]* Turlough Neary, Damien Woods. [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] — {{---}} ПО для изучения формальных языков, включает в себя эмулятор одноленточных и многоленточных машин Тьюринга с визуальным редактором.] [[Категория: Теория формальных языков]]