Машина Тьюринга: различия между версиями

''Недетерминированной машиной Тьюринга'' (сокращенно ''НМT'') <math>M</math> называется семерка

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

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

пустыми символами. ''Конфигурацией'' (или ''мгновенным описанием'') машины Тьюринга <math>M</math> называется слово вида <math>xqy</math>, где <math>xy</math> --- непустая часть ленты, а <math>q</math> --- текущее состояние управляющего устройства (головка на ленте обозревает символ,

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

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

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

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

в конечном и магазинном автоматах, но и бесконечной вспомогательной памяти последнего, причем без присущих [[МП- автомат|''МП-автомату'']] ограничений на "магазинный" характер ее использования.

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

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

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

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