Изменения

== Введение == '''Машина Тьюринга''' (англ. ''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> — всюду определённая функция перехода автомата.}}

{{Определение|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>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>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>.

Заменив у машины Тьюринга бесконечную в обе стороны ленту на бесконечную в одну сторону, мы не теряем в вычислительной мощности. По произвольной машине Тьюринга строится двухдорожечная машина с полубесконечной лентой .{{Теорема|author=|statement=Для любой машины Тьюринга существует эквивалентная машина Тьюринга, работающая на полубесконечной ленте.|proof=Существует алгоритм, по которому для любой машины Тьюринга может быть построена эквивалентная машина Тьюринга с объявленным свойством. Сначала занумеруем ячейки рабочей ленты машины Тьюринга с ''бесконечной лентой'' следующим образом: в первой ячейке записывается  [[Файл:Mt1.png]] Затем перенумеруем ячейки, и запишем символ <tex>c \in \mathbb TPi \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> позиция головки на ленте выше (считаем, что ленты нумеруются сверху вниз).