5

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

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

M = {

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

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

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

4

3 回答 3

8

尽管这是描述图灵机的一种非常非正式的方式，但我会说问题是以下之一：

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

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

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

于 2010-03-13T15:44:50.930 回答
1

我对图灵机有点生疏，但我相信你的推理是正确的，即整数集是无限的，因此你不能全部计算出来。我不确定如何从理论上证明这一点。

但是，了解图灵机的最简单方法是记住“任何真实计算机可以计算的东西，图灵机也可以计算。”。因此，如果您可以编写一个给定多项式的程序可以解决您的 3 个问题，那么您将能够找到一台图灵机也可以。

于 2010-03-12T20:34:25.343 回答
1

我认为问题出在最后一部分：otherwise reject.

根据可数集基础，可数集上的任何向量空间本身都是可数的。在您的情况下，您在 size 的整数上有一个向量空间n，这是可数的。所以你的整数集是可数的，因此可以尝试它们的每一种组合。（也就是说不漏掉任何组合。）

此外，计算p给定输入集的结果也是可能的。

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

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

于 2010-03-12T20:40:06.710 回答