Why is this an invalid Turing machine?

Question

Whilst doing exam revision I am having trouble answering the following question from the book, "An Introduction to the Theory of Computation" by Sipser. Unfortunately there's no solution to this question in the book.

Explain why the following is not a legitimate Turing machine.

M = {

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

1. Try all possible settings of x1, ..., xn to integer values
2. Evaluate p on all of these settings
3. If any of these settings evaluates to 0, accept; otherwise reject. }

This is driving me crazy! I suspect it is because the set of integers is infinite? Does this somehow exceed the alphabet's allowable size?

Thanks!

Answer 1

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.

Answer 2

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.

Answer 3

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.