为什么这是无效的图灵机的?

Question

虽然这样做的考试版本我无法回答下列问题的书"的介绍计算理论"通过Sipser.不幸的是没有解决这个问题的书。

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

M={

输入是多项式p超过变量x1,...,x

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

这是我疯狂!我怀疑它是因为设置的整数是无限的?不这在某种程度上超出字母的允许的尺寸？

Answer 1

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

• otherwise reject -我同意Welbog。因为你有一个数组无限的可能的设置，机器可以永远不知道是否设置在其它评估为0还没有到来，并将循环永远如果它找不到任何-只有当这样一个设定是遇到了，机器可能停止。这最后一个声明是无用的，将永远不会是真实的，当然，除非限制机器的一组有限的整数。

• 代码顺序：我会读这个伪为"的第一编写的所有可能的设置下来，然后评估p的每一个"有你的问题：再次，通过具有无限的可能的设置，甚至第一部分都不会终止，因为那里从来不是最后一定要写下来，继续下一个步骤。在这种情况下，甚至不可能的机从来不说"没有0设置"，但是它可能甚至从来没有开始评估以找到一个。这也将得到解决，通过限制整套。

无论如何，我不认为问题是字母的大小。你不会利用一个无限的字母，因为你整数可以写在小数点/binary/等，这些只能使用(非常)有限字母。

Answer 2

我有点生疏图灵机的，但是我相信你的推理是正确的，即该组整数是无限的，因此不能计算他们所有。我不知道如何证明这个理论上讲虽然。

但是，最简单的方式得到你的头图灵机的是要记住"任何一个真正的计算机可以计算、图灵机还可以计算。".所以，如果你可以写一个程序，给出多项式可以解决你的3个问题，你将能够找到一个图灵机的也可以这样做。

Answer 3

我想问题是有最后一部分： otherwise reject.

根据 可数的设置基础知识, ，任何一矢量的空间超过一个数集数本身。在你的情况，你有一个矢量的空间，在整数的大小 n, ，这是可数。所以你设置的整数是可数，因此能够尝试的每一个组合。(就是说没有丢失任何组合。)

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

和进入接受国时 p 计算结果为0也是可能的。

然而，由于有无数输入的向量，你可以 从来没有 拒绝的投入。因此，没有图灵机的能遵守所有的规则中定义的问题。没有那最后一条规则，它是可能的。