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

Опис

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

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

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

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

Визначення

Більш формально, недетермінована машина Тюрінга - це шістка об'єктів , де

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

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

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

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

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

Приклад

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

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

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

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

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

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

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

Джерела

Визначення та приклади машин Тюрінга Карпов Ю. П. Теория автоматов ISBN 5-318-00537-3