# Does this Turing Machine M decide the language of polynomials?

Does this Turing Machine decide language of polynomials with integer coefficients which have integer roots: The input represents a polynomial over variables x1, . . . , xn with integer coefficients.
1. Examine all possible integer values of x1, . . . , xn.
2. Evaluate the polynomial on all of them.
3. If any of them evaluates to 0, accept; else reject

From what I know I would say No, since: "M decides a language L iff M accepts all strings in L and reject all strings not in L ". Where L is the language of polynomials. Is this correct?
Any help is appreciated!

• I don't see a Turing machine anywhere in your question. However, it looks like you have an abstract description of an algorithm that accepts the polynomials with integer roots. However, it's not clear how you would examine all possible integer values as there may be infinitely many. – Tom van der Zanden Sep 28 '15 at 8:42
• I don't understand your reasoning. You just say, "No, because the definition of 'decides' is blah" without saying how the suggested algorithm fails to meet this definition. – David Richerby Sep 28 '15 at 8:45
• Hint: Hilbert's tenth problem. – David Richerby Sep 28 '15 at 8:46
• @TomvanderZanden I was given this task and I believe the 3 points describes an Turing Machine. – Julian H Sep 28 '15 at 8:50
• @DavidRicherby My reasoning makes no sense to me either anymore. I will read your hint and see if helps me understand – Julian H Sep 28 '15 at 8:58

• If the input polynomial is in $L$, the machine halts and answers YES.
• If the input polynomial is not in $L$, the machine never halts.
• If the input polynomial is in $L$, the machine halts and answers YES.
• If the input polynomial is not in $L$, the machine halts and answers NO.