Недетерминированная машина Тьюринга.

В дальнейшем для определения класса сложности NP потребуется определение недетерминированной машины Тьюринга (НДМТ или НТ). Схема недетерминированной машины Тьюринга:

* ...

-2 -1 0 1 2 n

УМ

Отличие от обычной машины Тьюринга заключается в том, что недетерминированная машина имеет дополнительно угадывающий модуль (УМ), который может только записывать на ленту слова из внешнего алфавита. Поскольку будем рассматривать НТ решающие только задачи распознавания (множество возможных решений этих задач «ДА» и «НЕТ»), то удобно считать, что машина имеет два заключительных состояния и , соответствующие ответам "ДА" и "НЕТ" соответственно. Работа машины имеет две стадии:

1-я стадия - угадывание. В начальный момент на ленте записано слово x= - код индивидуальной задачи I, начиная с ячейки 1. В ячейке 0 записан знак раздела * . Угадывающий модуль просматривает ячейку -1. Затем УМ пишет произвольное слово c(x) по одной букве за такт в каждой ячейке с номерами -1,-2,-3,... . В итоге 1-ой стадии конфигурацией машины будет c(x)* x.

2-я стадия - решение. На этой стадии недетерминированная машина работает как обычная машина Тьюринга в конфигурации c(x)* x. Если машина через конечное число шагов приходит в состояние , то говорим, что она принимает конфигурацию c(x)* x. Будем говорить, что недетерминированная машина принимает x, если существует слово c(x), что конфигурация c(x)* x принимается.