我不理解非确定性图灵机的概念。

Question

我不理解非确定性图灵机的概念。我猜我理解非确定性算法这个术语：（非确定性算法是一种算法，它在不同运行中可以展示出不同的行为，与确定性算法相反）。所以该算法可能是这样的：

a = fromSomeAlgo();

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

但对于 非确定性图灵机，我阅读到，它可以在给定的时间内处于多个状态。此外，维基百科文章指出："一个非确定性图灵机（NTM）可能有一组规则，针对给定情况提供多个操作"。

这是什么意思？..给定情况下有多个操作...多个状态...我根本不理解。

- Suhail Gupta

---

请查看http://www.cs.odu.edu/~toida/nerzic/390teched/tm/othertms.html并查看末尾的“Turing机器接受a +”。这是解决方案空间的更详细的模型。用“有形”的术语来说，一组并行处理器每个应用下一个状态的规则，并且它们彼此之间没有联系。 - ashley

我认为这些管理员关闭他们不喜欢的问题。谢谢管理员让Stack Overflow变得更加无用。 - DollarAkshay

@AkshayLAradhya：在我看来，这种问题更适合在计算机科学堆栈交换上讨论。 - Mario Cervera

Answer 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"。只有没有这样的计算时，它才会返回"false"。

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

Bonus:
请注意，所有可以通过非确定性图灵机实现的操作——也可以通过确定性图灵机实现（反之亦然）——例如，停机问题 在两者中均无法决定。然而，在非确定性图灵机上，NPC问题可以在多项式时间内解决，我们不知道（并且我们认为不能）如何在确定性图灵机上以多项式时间解决。

- amit

---

一个非确定性图灵机的存在与确定性图灵机同等程度。实际上，两者都不存在，因为所有真正的计算机都有有限的存储空间，但我们可以模拟它们。最大的区别在于，模拟非确定性图灵机所需的时间往往会呈指数级增长，而不是线性增长。模拟器必须跟踪机器在给定步骤结束时可能处于的所有配置。对于确定性图灵机的模拟器只需要一次跟踪一个配置。 - Patricia Shanahan

@PatriciaShanahan：这并不完全正确。虽然我们有“有限存储”，但RAM机器也可以使用磁盘来存储数据。可以在算法运行时动态增加磁盘上可存储的数据容量，但其数量受到一个非现实的数字的限制。然而，如果你试图硬着头皮去做，宇宙中原子的数量是有限的，因此可以达到的状态/配置数量也是有限的。 - amit

概念大幅简化了。我一直在苦苦思考这个问题，因为我遇到的大多数定义都太学术化，难以理解。 - Chris Walter

非确定性图灵机的概念纯粹是理论上的，目前并不存在非确定性图灵机。这对我们有很大帮助。 - roottraveller