Недетерминированная МТ

Это совершенно иное обобщение понятия МТ. Рассмотрим случай одноленточной недетерминированной машины Тьюринга (НМТ).

Имеется две управляющие головки (УГ) и одна лента. Одна головка Г1 - обычная, такая же, как в МТ, а вторая Г2, которая часто называется угадывающей, может только записывать. Запись на ленте представляет собой слово (условие задачи), записанное слева направо, начиная с ячейки с номером 1. В начальный момент времени обычная головка наблюдает ячейку с номером 1, а пишущая головка - ячейку с номером (-1). Вначале работает только пишущая (угадывающая) головка. На каждом такте работы она может написать символ в наблюдаемой ячейке и сдвинуться влево, либо остановиться. В последнем случае начинает работать обычная головка с состояния q₀. С этого момента НМТ работает точно так же, как МТ с той лишь разницей, что наблюдает не самый крайний слева символ входного слова.

Управляющее устройство пишущей головки принимает решение совершенно произвольно, поэтому может никогда не остановиться.

Ниже в разного рода определениях важна только возможность написания некоторого слова угадывающей головкой. Так как она пишет произвольно, то может написать любую букву в ячейке с номером -1, любую – в ячейке -2 и т.д. Если мы будем рассматривать все возможные результаты работы угадывающей головки, то это будут все возможные слова в данном алфавите.

Далее мы будем различать входное слово I и слово U, записанное угадывающей головкой.

Разница между МТ и НМТ может быть проиллюстрирована с помощью сравнения модели обычных вычислений и моделью параллельных вычислений.

В качестве примеров можно рассмотреть задачи о выполнимости, о гамильтоновом цикле и о простоте числа.

Дата добавления: 2015-07-11