Определение.

Формально машина Тьюринга определяется как следующая шестёрка:

Т = (V₁, V₂, Q, δ, q₀, F),

где V₁ = {a₁, ..., a_n} – входной алфавит (конечное множество символов);

V₂ = {А₁, ..., А_k, B} – конечное множество ленточных символов, которое в качестве своего подмножества содержит входной алфавит;

Q = {q₀ , q₁, ..., q_n-1} – конечное множество состояний;

q₀ ∈ Q – начальное состояние;

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

δ – функция, отображающая Q . V₂ в Q . V₂ – {B} . {Л, П}.

(Л и П – специальные символы, указывающие на направление движения головки, лево и право).

Отображение (функцию) δ удобно задавать совокупностью команд вида: (q, A) → (q′, A′, Л) либо (q, A) → (q′, A′, П).

Определение.

Ситуация машины Тьюринга Т – это тройка вида (q, β, i),

где q ∈ Q;

β = A₁, ..., A_n – часть ленты, не содержащая символов В (непустая часть ленты);

i = (0 ≤ i ≤ n+1) – расстояние ленточной (пишущей - читающей) головки от левого конца β; при i = 0 головка находится левее самого левого символа β, при i = n+1 – правее самого правого.

Рассмотрим произвольную ситуацию машины Т:

(q, A₁ ... A_i .... A_n, i), 1 ≤ i ≤ n.

Пусть среди команд отображения δ имеется следующая:

(q, A_i) → (q′, X, Л).

При этом возможно следующее движение (или элементарное действие) машины Тьюринга: головка стирает символ А_i, записывает вместо него символ Х и перемещается на одну ячейку влево.

Между старой и вновь возникшей ситуациями в этом случае существует отношение, которое записывается следующим образом:

(q, A₁ ... A_i .... A_n, i) ├ (q′, A₁ ... A_i-1 Х A_i+1.... A_n, i -1).

Символ ├ означает – «утверждается».

Аналогично для команды (q, A_i) → (q′, X, П) движение машины Тьюринга записывается как

(q, A₁ ... A_i .... A_n, i) ├ (q′, A₁ ... A_i-1 Х A_i+1.... A_n, i+1).

Кроме рассмотренной ситуации возможны и такие:

(q, A₁ ... A_n, 0);

(q, A₁ ... A_n, n+1).

К ним применимы команды вида:

(q, В) → (q′, X, Л) либо

(q, В) → (q′, X, П).

Первая из этих команд меняет указанные ситуации соответственно следующим образом:

(q, A₁ ... A_n, 0) ├ (q′, X A₁ ... A_n, 0);

(q, A₁ ... A_n, n+1) ├ (q′, A₁ ... A_n X, n).

Вторая из этих команд меняет их так:

(q, A₁ ... A_n, 0) ├ (q′, X A₁ ... A_n, 2);

(q, A₁ ... A_n, n+1) ├ (q′, A₁ ... A_n X, n+2).

Определение.

Если ситуации (q₁, β₁, i₁) и (q₂, β₂, i₂) связаны между собой некоторым числом элементарных действий, то между ними имеет место отношение:

(q₁, β₁, i₁) ├* (q₂, β₂, i₂).

Определение.

Язык, допускаемый машиной Тьюринга Т, это:

L(Т) = {α | α∈ V₁* ∧ (q₀, α, 1) ├* (q_f, β, i)},

где q_f = F, β ∈ V₂*, i ≥ 0.

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

Определение.

Так же как для автоматов введем понятие недетерминированной машины Тьюринга. Её отличие от детерминированной заключается в том, что функция δ отображает множество Q x V₂ в множество подмножеств

Q x (V₂ – {B}) x {Л, П}.

Определение.

Если язык L порождается грамматикой типа 0, то L допускается некоторой машиной Тьюринга. Верно и обратное, если язык L допускается некоторой машиной Тьюринга, то L порождается грамматикой типа 0.

7. Машины Тьюринга и линейно-ограниченные автоматы.

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

Определение.

Проблема разрешимости заключается в следующем. Пусть есть некоторая цепочка α на входе машины Тьюринга, которая допускает язык L. Всегда ли можно установить принадлежность цепочки α к языку L за конечное число элементарных действий этой машины?

Однако не для всех языков типа 0 эта проблема разрешима.

Другими словами, можно подобрать такой язык типа 0, что соответствующая ему машина Тьюринга для некоторой цепочки α за конечное число элементарных действий не сможет установить принадлежность ее к данному языку. Поэтому машина Тьюринга в общем виде не нашла применения в реальных кибернетических моделях; языки типа 0 также не используются.

Наибольший интерес представляют различные специальные классы машин Тьюринга, к которым можно отнести автоматы, рассмотренные выше, а также так называемые линейно-ограниченные автоматы, допускающие языки типа 1 (НС-языки).