World's most popular travel blog for travel bloggers.

# [Solved]: Does this Turing Machine M decide the language of polynomials?

, ,
Problem Detail:

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!

#### Answered By : Yuval Filmus

The problem with this algorithm is that it never terminates when the polynomial has no integer roots. Its semantics are:

• 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.

The semantics we are after are a bit different:

• 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.