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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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


Опис[ред.ред. код]

Детермінована машина Тюрінга має функцію переходу, яка по комбінації поточного стану і символу на стрічці визначає три речі: символ, що буде записаний на стрічці, напрямок зміщення головки по стрічці і новий стан скінченного автомату. Наприклад, 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 (2b-1≤N<2b) є складовим. Тоді b - довжина вхідних даних, стосовно якого розглядається час обчислення. Відповідь "ТАК" - число складене і "НІ" - просте.

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

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

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

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

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

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

Див. також[ред.ред. код]

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

Посилання[ред.ред. код]