Ответ 1
В не детерминированной машине Тьюринга в каждой ветки - вы делаете обе возможности - и только когда вы закончите, вы "выбираете", какой из них вам нужен для решения (если он существует).
Например, рассмотрим задачу суммирования подмножества с S = {a,b,c... }. Не детерминированная машина Тьюринга имеет линейное решение:
for each element:
"guess" if it is in the subset
check if the subset has the specified sum
Созданное дерево будет примерно таким:
start
with a without a
/ \ / \
/ \ / \
/ \ / \
with b without b with b without b
/ \ / \ / \ / \
with c without c with c without c with c without c with c without c
Достаточно, чтобы один расчет (путь в дереве) был правильным, чтобы алгоритм дал "true". Он дает "ложь" только в том случае, если такого расчета нет.
Понятие недетерминированной машины Тьюринга является чисто теоретическим - нет никакой недетерминированной машины для turing.
Bonus:
Обратите внимание, что все, что можно сделать с помощью не детерминированной машины Тьюринга, может быть выполнено с помощью детерминированной машины Тьюринга (и наоборот) - например, Halting Проблема не может быть определена. Однако проблемы NPC могут выполняться полиномиально в недетерминированных машинах Тьюринга, и мы не знаем (и предположим, что не можем), как это сделать полиномиально на детерминированных машинах Тьюринга.