(Notes from Chapter 4, Sections 1 - 3, 5)
Arrange the variables in the following order: \[Y~X_1~Z_1~X_2~Z_2~X_3~Z_3 \cdots.\] Do the same for the labels: \[A_1~B_1~C_1~D_1~E_1~A_2~B_2~C_2~D_2~E_2~A_3 \cdots.\]
\(\#(V)\) is the position of a given variable in the appropriate ordering For example, \(\#(X) = 2\), \(\#(Z_3) = 7\)
\(\#(L)\) is the position of a given label in the appropriate ordering For example, \(\#(E)= 5\), \(\#(B_2) = 7\).
For an instruction \(I\) of the language \({\cal S}\), \[ \#(I) = \langle a, \langle b, c\rangle \rangle\] where
\(a = 0\) if \(I\) is unlabelled and \(a = \#(L)\) if \(I\) is labelled \(L\);
\(c = \#(V) -1 \) if the variable \(V\) is mentioned in \(I\);
\(b = \left \{ \begin{array}{ll} 0 & \text{ if } V \leftarrow V \text{ is the statement in } I, \\ 1 & \text{ if } V \leftarrow V+1 \text{ is the statement in } I, \\ 2 & \text{ if } V \leftarrow V~\dot{-}~1 \text{ is the statement in } I, \\ \#(L')+2 & \text{ if } \textbf{if } V \neq 0 \textbf{ goto } L' \text{ is the statement in } I. \\ \end{array} \right.\)
The number of the labelled instruction \( [B] ~~~ X \leftarrow X + 1\) is \[ \langle 2, \langle 1, 1 \rangle \rangle = \langle 2, 5 \rangle = 2^2 (2\cdot 5 + 1)~\dot{-}~ 1 = 43.\]
The number of the unlabelled instruction \( Y \leftarrow Y\) is \[ \langle 0, \langle 0, 0 \rangle \rangle = 0.\]
Fact. For any given number \(q\), there is a unique instruction \(I\) with \(\#(I) = q\).
Note that \(l(q) = 0\) means the instruction is unlabelled. Otherwise, the label is the \(l(q)\)th from the list.
The index of the variable in the instruction is given by \(r(r(q))\). The actual statement is given by \(l(r(q))\).
For example, the instruction with number \(23 = \langle 3, \langle 2, 0 \rangle \rangle\) is \[[C]~~~ Y \leftarrow Y~\dot{-}~1.\]
To avoid ambiguity, we stipulate that the final instruction in a program cannot be the unlabelled statement \(Y \leftarrow Y\).
Let \({\cal P}\) be a program consisting of the instructions \(I_1,I_2,\ldots,I_k\). Then the number of \({\cal P}\) is \[ \#({\cal P}) = [\#(I_1),\#(I_2),\ldots,\#(I_k)] - 1.\]
Fact. Every number determines a unique program.
To determine the program whose number is \(255\), note that \(255 +1 = 2^8 = [8]\). Hence, the program has only one instruction whose number is \(8 = \langle 0, \langle 0, 2 \rangle \rangle\). The instruction is \( Z \leftarrow Z+1.\)
To determine the program whose number is \(1199\), note that \(1199 +1 = 2^4\cdot 3^1 \cdot 5^2 = [4,1,2]\). Now, \[4 = \langle 0, \langle 0, 1 \rangle \rangle\] \[1 = \langle 1, \langle 0, 0 \rangle \rangle\] \[2 = \langle 0, \langle 1, 0 \rangle \rangle.\] Hence, the program is \[ \begin{array}{ll} & X \leftarrow X \\ [A] & Y \leftarrow Y \\ & Y \leftarrow Y+1 \end{array} \] Hence, this program computes the function \(y = 1\).
The empty program has the number \(1 -1 = 0\).
We define \(\operatorname{HALT}(x,y)\) to be the predicate that holds if and only if the program whose number is \(y\) eventually halts on input \(x\).
Theorem 2.1. \(\operatorname{HALT}(x,y)\) is not a computable predicate.
For each \(n \gt 0\), define \[\Phi^{(n)}(x_1,\ldots,x_n,y) = \psi_{\cal P}^{(n)}(x_1,\ldots,x_n),~~~\text{where}~\#({\cal P}) = y.\]
Theorem 3.1 (Universality Theorem). For each \(n \gt 0\), the function \(\Phi^{(n)}(x_1,\ldots,x_n,y)\) is partially computable.
In other words, for each \(n \gt 0\), there is a program \({\cal U}_n\) that computes \(\Phi^{(n)}\). The programs \({\cal U}_n\) are called universal and they work very much like interpreters.
For each \(n \gt 0\), the sequence \[\Phi^{(n)}(x_1,\ldots,x_n,0), \Phi^{(n)}(x_1,\ldots,x_n,1),\ldots\] enumerates all partially computable functions of \(n\) variables. To emphasize this aspect, we write \[\Phi_y^{(n)}(x_1,\ldots,x_n)=\Phi^{(n)}(x_1,\ldots,x_n,y).\]
When \(n = 1\), the subscript is often omitted: \[\Phi_y(x) = \Phi(x,y) = \Phi^{(1)}(x,y).\]
Let \(\operatorname{SNAP}^{(n)}(x_1,\ldots,x_n,y,t)\) be the snapshot for program \(y\) on inputs \(x_1,\ldots,x_n\) after exactly \(t\) steps.
Fact. \(\operatorname{SNAP}^{(n)}(x_1,\ldots,x_n,y,t)\) is primitive recursive.
Define the predicates \[\operatorname{STP}^{(n)}(x_1,\ldots,x_n,t) \iff \begin{array}{l} \text{There is a computation of program } y \\ \text{of length } \leq t+1 \text{ beginning with inputs} \\ x_1,\ldots,x_n \end{array} \]
In other words, \(\operatorname{STP}^{(n)}(x_1,\ldots,x_n,t)\) holds if and only if program \(y\) halts after \(t\) or fewer steps on inputs \(x_1,\ldots,x_n\).
Theorem 3.2 (Step-Counter Theorem). For each \(n \gt 0\), the predicate \(\operatorname{STP}^{(n)}(x_1,\ldots,x_n,t)\) is primitive recursive.
Proof (sketch). Let \(\operatorname{TERM}(x,y) \iff l(x) \gt \operatorname{Lt}(y+1)\). Clearly, \(\operatorname{TERM}(x,y)\) is primitive recursive. The result follows from that \[\operatorname{STP}^{(n)}(x_1,\ldots,x_n,y,t) \iff \operatorname{TERM}(\operatorname{SNAP}^{(n)} (x_1,\ldots,x_n,y,t),y).\]
Theorem 3.3 (Normal form Theorem). Let \(f(x_1,\ldots,x_n)\) be a partially computable function. Then there is a primitive recursive predicate \(R(x_1,\ldots,x_n,y)\) such that \[f(x_1,\ldots,x_n) = l \left ( \mathop{\min}_z R(x_1,\ldots,x_n,z) \right ).\]
Proof (sketch). Let \(y_0\) be the number for a program that computes \(f(x_1,\ldots,x_n)\). We can then take \(R(x_1,\ldots,x_n,z)\) to be the predicate \begin{eqnarray*} & & \operatorname{STP}^{(n)}(x_1,\ldots,x_n, y_0, r(z)) \\ & \& & l(z) = (r(\operatorname{SNAP}^{(n)}(x_1,\ldots,x_n, y_0, r(z))))_1 \end{eqnarray*}
Theorem 3.4'. A function is partially computable if and only if it can be obtained from the initial functions by a finite number of applications of composition, recursion, and minimization (on functions).
When the function obtained from minimizatlion (on a predicate or a function) is a total function, we call the minimization proper.
Theorem 3.5. A function is computable (i.e. total) if and only if it can be obtained from the initial functions by a finite number of applications of composition, recursion, and proper minimization.
Theorem 5.1 (Parameter Theorem or \(s\)-\(m\)-\(n\) Theorem) For each \(n, m\gt 0\), there is a primitive recursive function \(S^n_m(u_1,u_2,\ldots,u_n,y)\) such that \[\Phi^{(m+n)}(x_1,\ldots,x_m,u_1,\ldots,u_n,y) = \Phi^{(m)}(x_1,\ldots,x_m, S_m^n(u_1,\ldots,u_n,y)).\]