Машини Тьюрінга. Обчислюваність за Тьюрінгом

Пiд (детермінованою) машиною Тьюрiнга (скорочено МТ) будемо розумiти впорядковану 5-ку (Q,T,d, q₀ ,q*), де:

- Q - скінченна множина внутрішніх станiв;

- T - скінченний алфавіт символів стрiчки, причому T мiстить спецiальний символ порожньої клiтки l;

- d : Q´T→Q´T´{R,L,e} - однозначна функція переходів;

- q₀ÎQ - початковий стан;

- q*ÎQ - фiнальний стан.

Функцiю переходiв на практицi задають скiнченною множиною команд одного з 3-х видiв: qa®pbR, qa®pbL та qa®pb, де p, qÎQ, a, bÎT, ®ÏQÈT. При цьому, як правило, не для всiх пар (q,a)ÎQ´T iснує команда з лiвою частиною qa. Це означає, що функцiя d не є тотальною. Проте зручніше вважати функцію d тотальною, тому для всiх пар (q,a)ÏD_d неявно (не додаючи вiдповiднi команди вигляду qa®qa) вводимо довизначення d(q,a)=(q,a,e).

Неформально МТ складається зі скiнченної пам’ятi, роздiленої на клiтки нескiнченної з обох бокiв стрiчки та головки читання-запису. В кожнiй клiтцi стрiчки мiститься єдиний символ iз T, причому в кожен даний момент стрiчка мiстить скiнченну кiлькiсть символiв, вiдмiнних вiд символа l. Головка читання-запису в кожен даний момент оглядає єдину клiтку стрiчки.

Якщо МТ знаходиться в станi q та головка читає символ a, то при виконаннi команди qa®pbR (команди qa®pbL, команди qa®pb) МТ переходить у стан p, замiсть символу a записує на стрiчцi символ b та змiщує головку на 1 клiтку направо (відповідно на 1 клiтку налiво, залишає головку на мiсцi).

Конфiгурацiя, або повний стан МТ, - це слово вигляду xqy, де x,yÎT*, qÎQ. Неформально це означає, що на стрiчцi записане слово xy, тобто злiва i справа вiд xy можуть стояти тiльки символи l, МТ знаходиться в станi q, головка читає 1-ий символ пiдслова y.

Конфiгурацiю вигляду q₀x, де 1-й та останнiй символи слова x вiдмiннi вiд l, називають початковою. Конфiгурацiю вигляду xq*y називають фiнальною. Пiсля переходу до фiнального стану, отже, до фiнальної конфiгурацiї МТ спиняється.

Нехай МТ знаходиться в конфiгурацiї xcqay, де x,yÎT*, a, cÎT, qÎQ. Пiсля виконання команди qa®pbR (команди qa®pbL, команди qa®pb) МТ перейде до конфiгурацiї xcbpy (вiдповiдно до конфiгурацiї xpcby, конфiгурацiї xcpby).

Кожна МТ задає вербальне вiдображення T* → T* таким чином.

МТ М переводить слово uÎT у слово vÎT*, якщо вона з початкової конфiгурацiї q₀u переходить до фiнальної конфiгурацiї xqy, де qÎF*, xy=avb, a, bÎ{l}* . При цьому перший та останнiй символи слова v вiдмiннi вiд l, або v=e. Цей факт записуємо так: v=M(u).

Якщо МТ M, починаючи роботу з початкової конфiгурацiї q₀u, нiколи не спиниться, кажуть, що M зациклюється при роботi над словом u. Тодi M(u)не визначене.

МТ M₁ та M₂ еквiвалентнi, якщо вони задають одне і те ж вербальне вiдображення.

МТ M обчислює часткову функцiю f:N^k→ N, якщо вона кожне слово вигляду переводить у слово у випадку (x₁,...,x_k)ÎD_f, та M( ) не визначене при (x₁,...,x_k)ÏD_f.

Функцiя називається обчислюваною за Тьюрiнгом, або МТ-обчислюваною, якщо iснує МТ, яка її обчислює.

Зауважимо, що кожна МТ обчислює безліч функцій натуральних аргументів та значень, але, зафіксовуючи наперед арність функцій, дістаємо, що кожна МТ обчислює єдину функцію заданої арності.

Розглянемо приклади МT.

Приклад 1. МТ, яка обчислює функцiю x+y:

q₀|® q₀|R

q₀#® q₀|R

q₀l® q₁lL

q₁| ® q*l

Приклад 2. МТ, яка обчислює функцiю f(x)=sg(x):

q₀l® q*l

q₀|® q₁|R

q₁|® q₁lR

q₁l® q*l

Приклад 3. МТ, яка обчислює функцiю f(x, y) =x-y:

q₀|® q₁lR

q₁|® q₁|R

q₁#® q₁#R

q₁l® q₂lL

q₂|® q₃lL

q₃|® q₃|L

q₃#® q₃#L

q₃l® q₀lR

q₂#® q*|

q₀#® q₄lR

q₄l® q*l

Приклад 4. МТ, яка обчислює функцiю f(x, y)=