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

В дальнейшем для определения класса сложности 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 принимается.

Проверочные вопросы и упражнения

1. Сформулируйте основные требования к алгоритмам и покажите, что этим требованиям удовлетворяет метод сложения двух целых чисел.

2. Постройте детерминированную машину Тьюринга, которая применима к любому входному слову.

3. Выделите сходства и различия детерминированной машины Тьюринга и недетерминированной машины Тьюринга.

4. Покажите, что всякую детерминированную машину Тьюринга можно рассматривать как частный случай недетерминированной машины Тьюринга.

5. Приведите примеры :

а) детерминированной машины Тьюринга;

б) недетерминированной машины Тьюринга.