recategorized by
234 views
2 votes
2 votes

Let $L$ be the following language.

$L=\left\{P\left(x_{1}, x_{2}, \ldots, x_{n}\right) \mid P\right.$ is a polynomial with an integral root $\}$.

Explain why the following Turing Machine description cannot decide the language $L$.

$\text{Description of M}:$ The input is a polynomial $P$ over the variables $x_{1}, \ldots, x_{n}$.

  • Try all possible settings of $x_{1}, \ldots, x_{n}$ to integer values.
  • Evaluate the polynomial on all values.
  • If any of these settings evaluate to $0,$ accept. Else, reject.
recategorized by

Please log in or register to answer this question.

Related questions

1 votes
1 votes
0 answers
1
1 votes
1 votes
0 answers
3
2 votes
2 votes
1 answer
4