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

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

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

: QT→T{R,L,} однозначна функцiя переходiв;

q0Q початковий стан;

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

Функцiю переходiв на практицi задають скiнченною множиною команд одного з 3-х видiв: qapbR, qapbL та qapb, де p, qQ, a, bT, QT. При цьому, як правило, не для всiх пар (q,a)QT iснує команда з лiвою частиною qa. Це означає, що функцiя не є тотальною. Проте зручніше вважати функцію тотальною, тому для всiх пар (q,a)D неявно (не додаючи вiдповiднi команди вигляду qaqa), вводимо довизначення (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, команди qapb) МТ переходить в стан p, замiсть символу a записує на стрiчцi символ b та змiщує голiвку на 1 клiтку направо (відповідно на 1 клiтку налiво, залишає голiвку на мiсцi).

Конфiгурацiя, або повний стан МТ це слово вигляду xqy, де x,yT*, qQ. Неформально це означає, що на стр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,yT*, a, cT, qQ. Пiсля виконання команди qapbR (команди qapbL, команди qapb) МТ перейде до конфiгурацiї xcbpy (вiдповiдно до конфiгурацiї xpcby, конфiгурацiї xcpby).

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

МТ М переводить слово uT в слово vT*, якщо вона з почат-кової конфiгурацiї q0u переходить до фiнальної конфiгурацiї xqy, де qF*,. При цьому перший та останн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дображення.

МТ M обчислює часткову функцiю f:Nk→N, якщо вона кожне слово вигляду переводить в слово у випадку (x1,...,xk)Df , та M( ) невизначене при (x1,...,xk)Df .

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

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

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