Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій, Детальна інформація

S(3)

J(0,0,1)

Т(4,0)

2. МАШИНИ ТЬЮРIНГА

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

\xF02D\xF020Q \xF02D\xF020скiнченна множина внутрiшнiх станiв;

\xF02D\xF020T \xF02D скiнченний алфавiт символiв стрiчки, причому T мiстить спецiальний символ порожньої клiтки (;

\xF02D\xF020( : Q(T\x2192Q(T({R,L,(} \xF02D однозначна функцiя переходiв;

\xF02D\xF020q0(Q \xF02D початковий стан;

\xF02D\xF020q*(Q \xF02D ф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я ( не є тотальною. Проте зручніше вважати функцію ( тотальною, тому для всiх пар (q,a)(D( неявно (не додаючи вiдповiднi команди вигляду qa(qa), вводимо довизначення ((q,a)=(q,a,().

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

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

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

Конфiгурацiю вигляду q0x, де 1-й та останнiй символи слова x вiдмiннi вiд (, називають початковою. Конф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* \x2192T* таким чином.

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

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

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

) невизначене при (x1,...,xk)(Df .

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

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

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

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

q0|( q0|R

q0#( q0|R

q0(( q1(L

q1| ( q*(

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