377 views
0 votes
0 votes

Explain why the following is not a description of a legitimate Turing machine.

$M_{bad} = “$ On input $\langle p \rangle,$ a polynomial over variables $x_{1},\dots,x_{k}:$

  1. Try all possible settings of $x_{1},\dots, x_{k}$ to integer values.
  2. Evaluate $p$ on all of these settings.
  3.  If any of these settings evaluates to $0$, accept; otherwise, reject.$”$

Please log in or register to answer this question.

Related questions