Solution Found!
Explain why the following is not a description of a
Chapter , Problem 3.7(choose chapter or problem)
Explain why the following is not a description of a legitimate Turing machine.
\(M_{\text {bad }}=\text { "On input }\langle p\rangle \text {, a polynomial over variables } x_{1}, \ldots, x_{k} \text { : }\)
1. Try all possible settings of \(x_{1}, \ldots, 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.”
Questions & Answers
QUESTION:
Explain why the following is not a description of a legitimate Turing machine.
\(M_{\text {bad }}=\text { "On input }\langle p\rangle \text {, a polynomial over variables } x_{1}, \ldots, x_{k} \text { : }\)
1. Try all possible settings of \(x_{1}, \ldots, 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.”
Step 1 of 2
Turing machines will decide and recognize the decidable/recognizable languages. Turing machines compute the changes in the current state and the content of the current tape. The Turing machine computes the current head location also. The computation of the language continues until the state becomes an accept or reject state.