Why is this an invalid Turing machine?

Question

During the exam revision, I have problems with the answer to the next question from Singer’s book “Introduction to Computational Theory”. Unfortunately, there is no solution to this issue in the book.

Explain why the following is not a legitimate Turing machine.

M = {

The input is a polynomial p over the variables x1, ..., xn

• Try all possible settings x1, ..., xn for integer values
• Rate p for all of these parameters.
• If any of these parameters evaluates to 0, accept; otherwise reject. }

It drives me crazy! I suspect this is because the set of integers is infinite? Does this somehow exceed the allowable size of the alphabet?

Answer 1

Although this is a fairly unofficial way of describing a Turing machine, I would say that the problem is this:

• otherwise reject - I agree with Welbog about this. Since you have an infinitely endless set of possible settings, the machine will never be able to know whether the parameter on which it evaluates to 0 will still be executed and will be executed forever if it is not found - only when such a setting is encountered can the machine stop. This last statement is useless and will never be true, unless, of course, you restrict the machine to a finite set of integers.

• Code order: I would read this pseudo-code as “first write down all the possible settings, and then evaluate p on each,” and there your problem is: Again, having an infinite set of possible settings, even the first part will not be completed, because it will never be the last setting to record and continue with the next step. In this case, even the machine cannot say "no setting 0", but it cannot even begin to evaluate it. This could also be solved by restricting the integer set.

Anyway, I don't think the problem is the size of the alphabet. You would not use the infinite alphabet, since your integers can be written in decimal / binary / etc, and they only use the (very) finite alphabet.

Answer 2

I'm a little rusty on cars, but I think your reasoning is correct, i.e. the set of integers is infinite, so you cannot calculate them. I am not sure how to prove this theoretically.

However, the easiest way to think about Turing machines is to remember "Everything that a real computer can calculate can also calculate a Turing machine." So, if you can write a program in which a polynomial can solve your 3 questions, you can find a Turing machine that can also do this.

Answer 3

I think the problem is in the very last part: otherwise reject.

According to the basics of a countable set , any vector space over a countable set is considered countable. In your case, you have a vector space over integers n , which is countable. Thus, your set of integers is countable, and so you can try each combination of them. (That is, not missing any combination.)

It is also possible to calculate the result of p on a given set of inputs.

And the inclusion of a receiving state when p is 0 is also possible.

However, since there are an infinite number of input vectors, you can never reject input. Therefore, no Turing machine can follow all the rules defined in the question. Without this last rule, it is possible.