我不理解非确定性图灵机的概念[关闭]

我不明白这个概念非确定性图灵机。我想我理解这个词非确定性算法:(非确定性算法是一种可以在不同的情况下表现出不同行为的算法 运行，而不是确定性算法。）所以该算法可能是这样的：

a = fromSomeAlgo();

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

But for 非确定性图灵机 I read https://stackoverflow.com/questions/3671429/why-are-np-problems-called-that-way-and-np-hard-and-np-complete，在给定时间它可以处于多种状态。也维基百科文章 http://en.wikipedia.org/wiki/Non-deterministic_Turing_machine建议“非确定性图灵机（NTM）可能有一组规则，规定了更多 而不是针对特定情况的一项行动”.

这意味着什么 ？...针对给定情况的多个操作...多个状态...我根本不明白这一点。

在非确定性图灵机中，在每个分支中 - 您都会执行两种可能性 - 并且只有当您完成时，您才能“选择”解决方案所需的一种（如果存在）。

例如，让我们看看子集和问题 http://en.wikipedia.org/wiki/Subset_sum_problem, with 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

只要一次计算（树中的路径）正确，算法就可以得出“真”结果。仅当没有此类计算时，它才会产生“假”。

非确定性图灵机的概念纯粹是理论上的——不存在可用的非确定性图灵机。

Bonus:
请注意，可以使用非确定性图灵机完成的所有操作 - 都可以使用确定性图灵机完成（反之亦然） - 例如，停机问题 http://en.wikipedia.org/wiki/Halting_problem两者都不可决定。然而，NPC 问题可以在非确定性图灵机中通过多项式来完成，而我们不知道（并且我们假设我们不能）如何在确定性图灵机上通过多项式来完成它。