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

Материал из WikiGrapp
Перейти к:навигация, поиск

Машина Тьюринга(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.