Машина Тьюринга

Машина Тьюринга(Turing machine) — одна из основных конструкций, которые были предложены для уточнения, или адекватной формализации, общего интуитивного понятия алгоритма.

Недетерминированной машиной Тьюринга (сокращенно НМT или просто МT) $\,M$ называется семерка $\,(Q,T,\Sigma,b,q_0,q_f,\delta)$, где

(1) $\,Q$ — конечное множество состояний управляющего устройства;

(2) $\,T$ — конечное множество символов на ленте;

(3) $\,\Sigma$ — множество входных символов, $\Sigma\subseteq T$;

(4) $\,b$ — пустой символ, $b\in T \setminus \Sigma$;

(5) $\,q_0$ — начальное состояние, $q_0\in Q$;

(6) $\,q_f$ — заключительное (или допускающее) состояние, $q_f\in Q$;

(7) $\,\delta$ — так называемая функция перехода — отображение множества $Q\times T$ в множество подмножеств в $Q\times T\times \{L, R, S\}$, где $\,L$ означает сдвиг головки по ленте влево, $\,R$ — вправо, $\,S$ — головка остается на месте.

Машина Тьюринга работает на неограниченной с обеих сторон ленте, разделяемой на ячейки, одну из которых обозревает головка. В любой момент времени все ячейки, кроме конечного числа, заняты пустыми символами. Конфигурацией (или мгновенным описанием) машины Тьюринга $\,M$ называется слово вида $\,xqy$, где $\,xy$ — непустая часть ленты, а $\,q$ — текущее состояние управляющего устройства (головка на ленте обозревает символ, стоящий справа от $\,q$).

Начальной конфигурацией $\,M$ называется конфигурация вида $\,q_0\omega$, где $\omega\in\Sigma^*$. Заключительная конфигурация — это конфигурация вида $\,xq_f y$.

Tакт работы машины Тьюринга $\,M$ представляется в виде бинарного отношения $\vdash_M$, определенного на конфигурациях, для которого $\alpha \vdash_M\beta$ в одном из трех следующих случаев:

(1) $\alpha=\gamma qX\omega, \beta=\gamma pY\omega, (p,Y,S) \in \delta(q,X)$ для некоторых $\gamma, \omega\in T^*$;

(2) $\alpha=\gamma qX\omega, \beta=\gamma Yp\omega, (p,Y,R) \in \delta(q,X)$ для некоторых $\gamma,\omega\in T^*$;

(3) $\alpha=\gamma ZqX\omega, \beta=\gamma pZY\omega, (p,Y,L) \in \delta(q,X)$ для некоторых $\gamma,\omega\in T^*$ .

$\,M$ допускает цепочку $\omega\in\Sigma^*$, если $\,q_0\omega\vdash^*_M\alpha$, где $\,\alpha$ - некоторая заключительная конфигурация с пустой лентой, так называемая допускающая конфигурация. Языком, допускаемым $\,M$ (обозначается $\,L(M)$), называют множество всех цепочек, допускаемых $\,M$.

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

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

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

В дополнение к естественной интерпретации машины Тьюринга как распознавателя, допускающего тот или иной язык, ее можно рассматривать как устройство, которое вычисляет некоторую функцию $\,f$. Аргументы этой функции кодируются на ленте в виде слова $\,X$ со специальным символом (маркером), отделяющим их друг от друга. Если машина Тьюринга останавливается с заключительной конфигурацией $\,vq_fw$, то слово $\,Y=vw$ рассматривается как код значения функции $\,f$, т.е. $\,f(X)=Y$.

Машина Тьюринга $\,M$ называется детерминированной (сокращенно ДМT), если для любых $q\in Q$ и $X\in T$ множество $\,\delta(q,X)$ содержит не более одного элемента.

Литература

• Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.

• Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. —

Новосибирск: НГУ, 1995.