Church-Turing thesis

We present RAM's in more detail. A RAM is defined by a list of instructions, numbered from 1 to $n$. An instruction is of one of the types shown in Figure 4.17. (Note: We only list the instructions in the form of using direct addressing. As discussed in the text, they can also use constants or indirect addressing.) Initially, all registers of a RAM contain

value 0, the output tape is "empty" (indicated by a special symbol, e.g., B), and the input tape contains a finite number of nonnegative integers $\left(n_{1}, \ldots , n_{k}\right)$, stored in cells 1 to $k$, and cell $k+1$ is empty. The RAM begins with instruction 1 and, after finishing each instruction $i$, it goes to instruction $i+1$ if instruction $i$ is one of the first seven types, or it goes to the instruction $j$ as defined in instruction $i$ if instruction $i$ is one of the last two types. The RAM halts when it reaches an instruction $k>n$.

For any RAM $M$, we let $L(M)=\left\{ \left(n_{1}, \ldots , n_{k}\right) \mid M\text{ halts on input }\left(n_{1}, \ldots , n_{k}\right)\right\}$. We say $M$ computes a function $f: \bigcup_{k=1}^{\infty } \mathbf{N}^{k} \rightarrow \bigcup_{k=1}^{\infty } \mathrm{N}^{k}$ if, on input $\left(n_{1}, \ldots , n_{k}\right), M$ halts with outputs $\left(m_{1}, \ldots , m_{\ell }\right)= f\left(n_{1}, \ldots , n_{k}\right)$.

Explain why the following is not a description of a legitimate Turing machine. $M_{\text{bad }}=$ "On input $\langle p\rangle$, a polynomial over variables $x_{1}, \ldots , x_{k}$ :

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."