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

Question

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

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

M = {

的输入是在变量x1一个多项式p，...，XN

1. 尝试X1的所有可能的设置，...，x N为整数值
2. 在所有这些设置上评估p
3. 如果这些设置中的任何一个评估为0，则接受;否则拒绝。 }

这让我疯狂！我怀疑这是因为这组整数是无限的？这是否超出了字母表的允许大小？

Answer 1

虽然这是描述一个图灵机的相当非正式的方式，我想说的问题是下列之一：

• otherwise reject - 我Welbog同意这一点。由于您拥有数量可能无限的可能设置，因此机器无法知道其评估值为0的设置是否还会到来，并且如果未找到任何设置，将永远循环 - 只有遇到此类设置时，机器可能会停止。最后的陈述是无用的，永远不会是真的，除非你将机器限制在一个有限的整数集合中。代码顺序：我会读这个伪代码为“首先写下所有可能的设置，然后评估每个可能的设置”，并且存在您的问题： 再次，通过拥有无限可能的设置集，甚至不需要第一部分将永远终止，因为从来没有最后的设置写下来并继续下一步。在这种情况下，机器甚至不会说“没有0设置”，但它甚至不能开始评估以找到一个。这也可以通过限制整数集来解决。

无论如何，我不认为问题是字母表的大小。你不会使用无限的字母表，因为你的整数可以用十进制/二进制/等写成，而那些只使用（非常）有限的字母表。

Answer 2

我在图灵机上有点生疏，但我相信你的推理是正确的，即整数集是无限的，因此你不能计算它们。我不知道如何从理论上证明这一点。然而，让你的头在图灵机周围的最简单的方法是记住“真实计算机可以计算的任何东西，图灵机也可以计算。”。所以，如果你可以编写一个给定多项式的程序可以解决你的3个问题，你将能够找到一个也可以做到的图灵机。

Answer 3

我认为这个问题是非常最后一部分：otherwise reject.

据countable set basics，在数集的任何向量空间是可数的本身。在你的情况下，你有一个整数大小为n的向量空间，这是可数的。所以你的整数集是可数的，因此可以尝试它们的每个组合。 （也就是说不会错过任何组合）。

而且，在给定的一组输入上计算p的结果也是可能的。

并且当p评估为0时进入接受状态也是可能的。

但是，由于存在无限数量的输入向量，因此您可以从不拒绝输入。因此，图灵机不能遵循问题中定义的所有规则。没有最后的规则，这是可能的。