Недетермінована машина Тюрінга

В теоретичній інформатиці недетермінована машина Тюрінга — машина Тюрінга, функція переходу якої являє собою недетермінований скінченний автомат.

Опис

Детермінована машина Тюрінга має функцію переходу, яка по комбінації поточного стану і символу на стрічці визначає три речі: символ, що буде записаний на стрічці, напрямок зміщення головки по стрічці і новий стан скінченного автомату. Наприклад, X на стрічці в стані 3 однозначно визначає перехід в стан 4, запис на стрічку символу Y і ​​переміщення головки на одну позицію вліво.

Демонстрація роботи машини Тюрінга

У випадку з недетермінованою машиною Тюрінга, комбінація поточного стану автомата і символу на стрічці може допускати кілька переходів. Наприклад, X на стрічці і стан 3 допускає як стан 4 із записом на стрічку символу Y та зміщенням головки вправо, так і стан 5 з записом на стрічку символу Z і зміщенням головки вліво.

Як НМТ «дізнається», який з можливих шляхів приведе в потрібний стан? Є два способи це уявити.

• Можна вважати, що НМТ - «надзвичайно щаслива»; тобто завжди вибирає перехід, який зрештою приводить до потрібного стану, якщо такий перехід взагалі є.
• Можна уявити, що в разі неоднозначності переходу (поточна комбінація стану і символу на стрічці допускає кілька переходів) НМТ ділиться на кілька НМТ, кожна з яких діє за одним з можливих переходів.

Тобто на відміну від ДМТ, яка має єдиний «шлях обчислень», НМТ має «дерево обчислень» (у загальному випадку - експоненціальне число шляхів).

Визначення

Більш формально, недетермінована машина Тюрінга - це шістка об'єктів ${\displaystyle M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta )}$, де

• ${\displaystyle Q}$ — скінченна множина станів
• ${\displaystyle \Sigma }$ — скінченна множина символів (алфавіт стрічки)
• ${\displaystyle \iota \in Q}$ — початковий стан
• ${\displaystyle \sqcup }$ — символ пропуску (${\displaystyle \sqcup \in \Sigma }$)
• ${\displaystyle A\subseteq Q}$ — скінченна множина можливих станів
• ${\displaystyle \delta :Q\backslash A\times \Sigma \rightarrow \left(Q\times \Sigma \times \{L,R\}\right)}$ — багатозначне відображення з пари стан-символ, що називається функцією переходу.

Еквівалентність з ДМТ

Інтуїтивно здається, що НМТ більш потужні, ніж ДМТ, бо вони виконують кілька обчислень відразу. ДМТ може моделювати будь-який перехід НМТ, роблячи багаторазові копії стану, якщо зустрічається неоднозначність.

Очевидно, що це моделювання вимагає значно більше часу. Наскільки більше - невідомо. В окремому випадку обмеження за часом у вигляді полінома від довжини входу це питання являє собою класичну задачу «P = NP» (див. класи складності P і NP).

Клас алгоритмів, виконуваних за поліноміальний час на недетермінованих машинах Тюрінга, називається класом NP.

Приклад

Розглянемо задачу перевірки того що дане b-розрядне ціле число N (2^b-1≤N<2^b) є складовим. Тоді b — довжина вхідних даних, стосовно якого розглядається час обчислення. Відповідь «ТАК» — число складене і «НІ» — просте.

Недетермінований алгоритм для цього завдання може бути таким:

• Вибрати недетермінованої ціле число m таке що 1 < m < N.
• Розділити націло N на m, залишок позначимо через a.
• Якщо a = 0 видати відповідь «ТАК» (m тоді — дільник N), інакше видати відповідь «НІ».

(Алгоритм написаний не безпосередньо у вигляді визначення машини Тьюринга.)

Під час обчислення цього алгоритму визначальною частиною є час виконання ділення, яке може бути виконано за (b²) кроків, що являє собою поліноміальний час. Таким чином завдання знаходиться в класі NP.

Для реалізації такого часу обчислення, потрібно вдало вибирати число m, або виконувати обчислення по всіх можливих шляхах (для всіх можливих m) одночасно на безлічі копій машини.

Якщо моделювати цей алгоритм на детермінованій машині Тюрінга, пробуючи по черзі всі можливі варіанти, потрібно перевірити N-2=O(2^b) гілок. Таким чином загальний час обчислень буде O(b²2^b) кроків, що є вже експоненціальне час, яке істотно більше ніж поліноміальний час. Таким чином цей алгоритм не потрапляє в клас P. (Проте, можуть бути застосовані інші, більш швидкі алгоритми для цього завдання, які працюють за поліноміальний час, і таким чином завдання потрапляє в клас P.)

Див. також

Інші абстрактні виконавці та формальні системи обчислень:

• Машина Тюрінга
• Машина Поста (автоматною програмування)
• Лямбда-числення (функціональне програмування)

Джерела

• Hopcroft, John E.; ; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.)
• (інші мови). Теория рекурсивных функций и эффективная вычислимость. — М. : Мир, 1972. — 416 с.(рос.)
• Визначення та приклади машин Тюрінга [ 2 січня 2010 у Wayback Machine.]
• Карпов Ю. П. Теория автоматов