Why is this an invalid Turing machine? [closed]

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?

Answer 1

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.