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

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

Опис

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

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

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

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

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

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

Визначення

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

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

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

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

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

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

Приклад

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

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

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

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

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

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

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

Див. також

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

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

Джерела

• Шаблон:Cinderella Book
• Шаблон:Роджерс.Теорія рекурсивних функцій
• Визначення та приклади машин Тюрінга Шаблон:Webarchive
• Карпов Ю. П. Теория автоматов ISBN 5-318-00537-3