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

Формально машина Тьюринга (Tm) - это

, где

Q - конечное множество состояний;

- множество заключительных состояний;

- множество допустимых ленточных символов; один из них, обычно обозначаемый B, - пустой символ

- множество входных символов, подмножество \Gamma, не включающее B,

D функция переходов, отображение из

для некоторых аргументов функция D может быть не определена.

- начальное состояние.

Рис. 2.2.  Машина Тьюринга

Так определенная машина Тьюринга называется детерминированной. Недетерминированная машина Тьюринга для каждой пары

может иметь несколько возможных переходов. В начале n ячеек ленты содержат вход , остальная часть ленты содержит пустые символы. Обозначим конфигурацию машины Тьюринга как , где - текущее состояние, i - выделенный элемент строки, "положение головки" , w - текущее содержимое занятого участка ленты. Если головка сдвигается с ячейки, машина должна записать в нее символ, так что лента всегда состоит из участка, состоящего из конечного числа непустых символов и бесконечного количества пустых символов.

Шаг Tm определим следующим образом.

Пусть (q, A1, A2, ... An, i) - конфигурация Tm,

где

.

Если

и D(q, Ai) = (p, A, R)

(R от англ. Right), то

и)

То есть Tm печатает символ A и передвигается вправо.

Если

и

(L от англ. Left), то если i = n, то допустимо A = B и

Tm печатает A и передвигается влево, но не за конец ленты.

Если i = n + 1, головка просматривает пустой символ B.

Если D(q, B) = (p, A, R), то

и

Если D(q, B) = (p, A, L), то допустимо A=B и

Если две конфигурации связаны отношением

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

Язык, допускаемый Tm, это множество таких слов из T*, которые будучи расположены в левом конце ленты переводят Tm из начального состояния q0 с начальным положением головки в самом левом конце ленты в конечное состояние. Формально, язык, допускаемй Tm, это

Если Tm распознает L, то Tm останавливается, то есть не имеет переходов после того, как слово допущено. Однако, если слово не допущено, возможно, что Tm не останавливается.

Язык, допускаемый некоторой Tm, называется рекурсивно перечислимым. Если Tm останавливается на всех входах, то говорят, что Tm задает алгоритм и язык называется рекурсивным.

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

Содержание раздела

---

---