我不明白的非确定型图灵机的概念。 我想我懂术语不确定性的算法 ：（非确定性算法是可以在不同的运行表现出不同的行为的算法，而不是确定的算法）。因此算法也能像：
a = fromSomeAlgo();
if(a > foo)
stateA();
else
stateB();
但是对于非确定性图灵机我读 ，它可以在给定的时间是在一个以上的国家。 另外一个维基百科的文章提出“非确定性图灵机（NTM），可能有一组规则，规定了特定情况下多个动作”。
那是什么意思 ？ ..更多比一个给定的stituation一个动作......多种状态......我只是不明白这一点。
在一个非确定型图灵机，在每一个分支 - 你做的这两种可能性 - 只有当你完成你“选择”哪一个是你需要的解决方案之一（如果存在的话）。
例如，让我们来看看子集和问题 ，以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
，这就够了一个计算（树路径）的正确性，从而使算法产生“真实”。 它产生的“假”只是，如果没有这样的计算。
非确定性图灵机的概念是纯粹的理论 - 没有可用的非确定性图灵机。
奖金：
需要注意的是一切都可以用非确定型图灵机来完成-可以用确定性图灵机（或相反）来完成-例如， 停机问题也不会被decideable英寸 然而，NPC问题可以多项式非确定性图灵机做的，我们不知道（我们假设我们不能够）怎么办呢多项式在确定性图灵机。
