Although this is quite an informal way of describing a Turing machine, I'd say the problem is one of the following:
otherwise reject - i agree with Welbog on that. Since you have a countably infinite set of possible settings, the machine can never know whether a setting on which it evaluates to 0 is still to come, and will loop forever if it doesn't find any - only when such a setting is encountered, the machine may stop. That last statement is useless and will never be true, unless of course you limit the machine to a finite set of integers.
The code order: I would read this pseudocode as "first write all possible settings down, then evaluate p on each one" and there's your problem: Again, by having an infinite set of possible settings, not even the first part will ever terminate, because there never is a last setting to write down and continue with the next step. In this case, not even can the machine never say "there is no 0 setting", but it can never even start evaluating to find one. This, too, would be solved by limiting the integer set.
Anyway, i don't think the problem is the alphabet's size. You wouldn't use an infinite alphabet since your integers can be written in decimal / binary / etc, and those only use a (very) finite alphabet.
I'm a bit rusty on turing machines, but I believe your reasoning is correct, ie the set of integers is infinite therefore you cannot compute them all. I am not sure how to prove this theoretically though.
However, the easiest way to get your head around Turing machines is to remember "Anything a real computer can compute, a Turing machine can also compute.". So, if you can write a program that given a polynomial can solve your 3 questions, you will be able to find a Turing machine which can also do it.
I think the problem is with the very last part: otherwise reject.
According to countable set basics, any vector space over a countable set is countable itself. In your case, you have a vector space over the integers of size n, which is countable. So your set of integers is countable and therefore it is possible to try every combination of them. (That is to say without missing any combination.)
Also, computing the result of p on a given set of inputs is also possible.
And entering an accepting state when p evaluates to 0 is also possible.
However, since there is an infinite number of input vectors, you can never reject the input. Therefore no Turing machine can follow all of the rules defined in the question. Without that last rule, it is possible.
发布评论
评论（3）
虽然这是描述图灵机的一种非常非正式的方式，但我认为问题是以下之一：
否则拒绝- 我同意 Welbog 的观点。由于您有一组可数无限的可能设置，因此机器永远无法知道其评估结果为 0 的设置是否还会出现，并且如果找不到任何设置，则将永远循环 - 仅当遇到此类设置时，机器可能会停止。最后一个陈述是无用的，永远不会是真的，除非你将机器限制为有限的整数集。代码顺序：我会将此伪代码读为“首先写下所有可能的设置，然后对每个设置进行评估”，这就是您的问题：
同样，通过拥有无限组可能的设置，即使第一部分也永远不会终止，因为永远不会有最后一个设置可以写下来并继续下一步。在这种情况下，机器甚至不能说“没有 0 设置”，但它甚至不能开始评估以找到一个。这也可以通过限制整数集来解决。
无论如何，我不认为问题在于字母表的大小。您不会使用无限字母表，因为您的整数可以用十进制/二进制/等书写，而这些只使用（非常）有限的字母表。
Although this is quite an informal way of describing a Turing machine, I'd say the problem is one of the following:
otherwise reject- i agree with Welbog on that. Since you have a countably infinite set of possible settings, the machine can never know whether a setting on which it evaluates to 0 is still to come, and will loop forever if it doesn't find any - only when such a setting is encountered, the machine may stop. That last statement is useless and will never be true, unless of course you limit the machine to a finite set of integers.The code order: I would read this pseudocode as "first write all possible settings down, then evaluate p on each one" and there's your problem:
Again, by having an infinite set of possible settings, not even the first part will ever terminate, because there never is a last setting to write down and continue with the next step. In this case, not even can the machine never say "there is no 0 setting", but it can never even start evaluating to find one. This, too, would be solved by limiting the integer set.
Anyway, i don't think the problem is the alphabet's size. You wouldn't use an infinite alphabet since your integers can be written in decimal / binary / etc, and those only use a (very) finite alphabet.
我对图灵机有点生疏，但我相信你的推理是正确的，即整数集是无限的，因此你无法计算全部。但我不确定如何从理论上证明这一点。
然而，了解图灵机的最简单方法是记住“任何真正的计算机可以计算的东西，图灵机也可以计算”。所以，如果你能编写一个程序，给定一个多项式可以解决你的 3 个问题，你将能够找到一台也能做到这一点的图灵机。
I'm a bit rusty on turing machines, but I believe your reasoning is correct, ie the set of integers is infinite therefore you cannot compute them all. I am not sure how to prove this theoretically though.
However, the easiest way to get your head around Turing machines is to remember "Anything a real computer can compute, a Turing machine can also compute.". So, if you can write a program that given a polynomial can solve your 3 questions, you will be able to find a Turing machine which can also do it.
我认为问题出在最后一部分：
否则拒绝。根据可数集合基础知识，可数集合上的任何向量空间本身都是可数的。在你的例子中，你有一个大小为 n 的整数的向量空间，它是可数的。所以你的整数集是可数的，因此可以尝试它们的每种组合。 （也就是说，不会丢失任何组合。）
此外，在给定的一组输入上计算 p 的结果也是可能的。
当
p计算结果为 0 时进入接受状态也是可能的。但是，由于输入向量的数量是无限的，因此您永远无法拒绝输入。因此，没有图灵机可以遵循问题中定义的所有规则。如果没有最后一条规则，这是可能的。
I think the problem is with the very last part:
otherwise reject.According to countable set basics, any vector space over a countable set is countable itself. In your case, you have a vector space over the integers of size
n, which is countable. So your set of integers is countable and therefore it is possible to try every combination of them. (That is to say without missing any combination.)Also, computing the result of
pon a given set of inputs is also possible.And entering an accepting state when
pevaluates to 0 is also possible.However, since there is an infinite number of input vectors, you can never reject the input. Therefore no Turing machine can follow all of the rules defined in the question. Without that last rule, it is possible.