Подтвердить что ты не робот

Я не понимаю концепцию недетерминированной машины Тьюринга

Я не понимаю концепцию недетерминированной машины Тьюринга. Я предполагаю, что я понимаю термин Недетерминированный алгоритм: (недетерминированный алгоритм - это алгоритм, который может проявлять разные поведения на разных работает, в отличие от детерминированного алгоритма.) Таким образом, алгоритм может быть следующим:

a = fromSomeAlgo();

if(a > foo)
   stateA();
else
   stateB();

Но для недетерминированной машины turing я прочитал, она может быть в нескольких состояниях в данный момент времени. Кроме того, статья в википедии предлагает:" Недетерминированная машина Тьюринга (NTM) может иметь набор правил, которые предписывают больше чем одно действие для данной ситуации ".

Что это значит?.. Более одного действия для данной ситуации... нескольких состояний... Я просто этого не понимаю.

Ответ 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 могут выполняться полиномиально в недетерминированных машинах Тьюринга, и мы не знаем (и предположим, что не можем), как это сделать полиномиально на детерминированных машинах Тьюринга.