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

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

Опис

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

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

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

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

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

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

Визначення

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

$Q$ — скінченна множина станів
$\Sigma$ — скінченна множина символів (алфавіт стрічки)
$\iota \in Q$ — початковий стан
$\sqcup$ — символ пропуску ( $\sqcup \in \Sigma$ )
$A\subseteq Q$ — скінченна множина можливих станів
$\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$ ), інакше видати відповідь «НІ».

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

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

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

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

Див. також

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

Джерела

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

Це незавершена стаття з інформатики.
Ви можете допомогти проєкту, виправивши або дописавши її.