World's most popular travel blog for travel bloggers.

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

, , No Comments
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!

Asked By : Julian H

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.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47642

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback