3
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Tom van der Zanden Sep 28 '15 at 8:42
  • 3
    $\begingroup$ 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. $\endgroup$ – David Richerby Sep 28 '15 at 8:45
  • 1
    $\begingroup$ Hint: Hilbert's tenth problem. $\endgroup$ – David Richerby Sep 28 '15 at 8:46
  • $\begingroup$ @TomvanderZanden I was given this task and I believe the 3 points describes an Turing Machine. $\endgroup$ – Julian H Sep 28 '15 at 8:50
  • $\begingroup$ @DavidRicherby My reasoning makes no sense to me either anymore. I will read your hint and see if helps me understand $\endgroup$ – Julian H Sep 28 '15 at 8:58
1
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ Does that mean that the Turing Machine can not decide any langauge since it never halts? And to make sure, that it accepts or rejects doesn't insinuate that it also halts? $\endgroup$ – Julian H Sep 28 '15 at 9:05
  • $\begingroup$ That's right, the language decided by a machine is only defined when the machine always halts. A Turing machine accepts if it halts and signals somehow YES (there are several equivalent mechanisms for this, such as writing output or going to an accepting halting state). It rejects if it halts and signals NO. $\endgroup$ – Yuval Filmus Sep 28 '15 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.