Недетерминированная машина Тьюринга
Недетерминированная машина Тьюринга (НМТ) — машина Тьюринга, функция перехода которой представляет собой недетерминированный конечный автомат (НКА).
Детерминированная (обычная, классическая) машина Тьюринга имеет функцию перехода, которая по комбинации текущего состояния и символа на ленте определяет три элемента: символ, который будет записан на ленте, направление смещения головки по ленте и новое состояние конечного автомата. Например, X на ленте в состоянии 3 однозначно определяет переход в состояние 4, запись на ленту символа Y и перемещение головки на одну позицию влево.
В случае недетерминированной машины Тьюринга, комбинация текущего состояния автомата и символа на ленте может допускать одновременно параллельно несколько переходов в следующие состояния. Например, X на ленте и состоянии 3 допускает как состояние 4 с записью на ленту символа Y и смещением головки вправо, так и состояние 5 с записью на ленту символа Z и смещением головки влево. Таким образом недетерминированная машина Тьюринга может одновременно находиться во многих состояниях.
В отличие от детерминированной машины Тьюринга, которая имеет единственный «путь вычислений», недетерминированный вариант имеет «дерево вычислений» (в общем случае — экспоненциальное число путей). Говорят, что недетерминированная машина Тьюринга принимает входные данные, если какая-нибудь ветвь этого дерева останавливается в допускающем состоянии, иначе НМТ входные данные отвергает. (Таким образом, ответы «да» и «нет» в случае недетерминированных вычислений несимметричны.)
Формально, недетерминированная машина Тьюринга задаётся в виде упорядоченной шестёрки элементов некоторых множеств:, где:
Несмотря на кажущуюся большую мощность недетерминированных машин в связи с тем, что они выполняют несколько возможных вычислений сразу (требуя только, чтобы хоть одно из них заканчивалось в допускающем состоянии), любой язык, допускающийся недетерминированной машиной Тьюринга, также допускается и обычной детерминированной машиной Тьюринга, поскольку она может моделировать любой недетерминированный переход, делая многократные копии состояния, если встречается неоднозначность.