Question

Explain why the following is not a description of a legitimate Turing machine. ${\mathbf{M}}_{\mathrm{bad}}\mathbf{=}$ “On input (p), a polynomial over variables${\mathbf{x}}_1,...,{\mathbf{x}}_k:$

1. Try all possible settings of ${\mathbf{x}}_1,...,{\mathbf{x}}_k:$to integer values.

2. Evaluate $\mathit{p}$ on all of these settings.

3. If any of these settings evaluates to 0, accept; otherwise, reject.”

Short answer

The machine requires all possible numbers as input. This is not a legitimate Turing machine because they have not been provided.

Step-by-step solution

Explain Turing machine

A Turing machine is a computer programme that, in theory, uses a table of rules to manipulate symbols on a tape strip. The Turing machine is a simple machine, it is made to mimic the logic of any computer algorithm. It is also very helpful for explaining how a computer's CPU works.

Define Legitimate Turing machine

Turing machines decides 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 acceptorrejectstate.

The description does not provide an upper bound for integer values the Turing Machine must check, so it is possible that it is never stop checking values. Therefore, there is no point where$M_{bad}$ rejects.

To complete the calculation, the aforementioned machine requires all possible numbers as input. This is not a legitimate Turing machine because they have not been provided.

Hence, the given Turing Machine does not have a legitimate description.