state-machine - 为什么这是一个无效的图灵机？

Question

在进行考试复习时，我无法回答 Sipser 所著的“计算理论导论”一书中的以下问题。不幸的是，书中没有解决这个问题。

解释为什么以下不是合法的图灵机。

M = {

输入是变量 x1, ..., xn 上的多项式 p

尝试所有可能的 x1, ..., xn 设置为整数值

在所有这些设置上评估 p

如果这些设置中的任何一个评估为 0，则接受；否则拒绝。
}

这真让我抓狂!我怀疑这是因为整数集是无限的？这是否超出了字母表的允许大小？

Answer 1

虽然这是描述图灵机的一种非正式的方式，但我认为问题在于以下之一:

otherwise reject - 我同意 Welbog 的观点。由于您有一组可数无限的可能设置，因此机器永远无法知道它评估为 0 的设置是否仍然存在，并且如果找不到任何设置，它将永远循环 - 只有在遇到这样的设置时，机器可能会停止。最后一个陈述是无用的，永远不会为真，除非您将机器限制为有限的整数集。

代码顺序:我会将此伪代码读为“首先写下所有可能的设置，然后对每个设置进行评估”，这就是您的问题:
同样，通过拥有无限的可能设置集，即使是第一部分也不会终止，因为永远不会有最后一个设置要记下并继续下一步。在这种情况下，机器甚至永远不会说“没有 0 设置”，但它甚至永远无法开始评估以找到一个。这也可以通过限制整数集来解决。

无论如何，我认为问题不在于字母表的大小。您不会使用无限字母表，因为您的整数可以用十进制/二进制等书写，而那些只使用(非常)有限的字母表。