(Notes from Chapter 2, Sections 1 - 4)
Language \(\cal{S}\)
Input variables: \(X_1,X_2,X_3,\ldots\)
Output variable: \(Y\)
Local variables: \(Z_1,Z_2,Z_3,\ldots\)
Labels: \(A_1,B_1,C_1,D_1,E_1,A_2,B_2,C_2,D_2,E_2,A_3,\ldots\)
the subscript 1 is often omitted; i.e. \(X\) means \(X_1\), \(Z\) means \(Z_1\), \(A\) means \(A_1\).
\(Y\) and the local variables have initial value 0.
The value of a variable is written in lowercase italics. e.g. \(x_5\) is the value of \(X_5\).
A statement is one of the following: \[ \begin{array}{l} V \leftarrow V + 1 \\ V \leftarrow V ~\dot{-}~ 1 \\ V \leftarrow V \\ \textbf{if } V \neq 0 \textbf{ goto } L \end{array} \] where \(V\) may be any variable and \(L\) may be any label.
An instruction is either a statement or \([L]\) followed by a statement where \(L\) is a label.
A program of \(\cal{S}\) consist of a list (a finite sequence) of instructions. The length of this list is called the length of the program.
The following program copies the value of \(X\) to \(Y\): \[ \begin{array}{ll} [A] & \textbf{if } X \neq 0 \textbf{ goto } B \\ & Z \leftarrow Z+1 \\ & \textbf{if } Z \neq 0 \textbf{ goto } E \\ [B] & X \leftarrow X~\dot{-}~1 \\ & Y \leftarrow Y+1 \\ & Z \leftarrow Z+1 \\ & \textbf{if } Z \neq 0 \textbf{ goto } A \\ \end{array} \]
The state of a program \({\cal P}\) is a list of equations of the form \(V = m\), where \(V\) is a variable and \(m\) is a natural number, that includes an equation for each variable that occurs in \({\cal P}\) and includes no two equations with the same variable. For example, for the program above, any state must include equations fo the variables \(Y\), \(X\), and \(Z\).
Note that the definition does not exclude equations with variables not in \({\cal P}\). For example, \[X = 4, Y = 3, Z =3\] and \[X_1 = 4, X_2 = 1, Y = 5, Z_1 =3, Z_2 = 5\] are both states of the above program, but \[X = 4, Y = 1\] is not since there is no equation in \(Z\).
Note also that the definition does not require the state can be “attained” from some initial state.
The value of the variable \(V\) at the state \(\sigma\) is the number \(q\) such that the equation \(V = q\) is one of the equations in \(\sigma\).
A snapshot of a program \({\cal P}\) of length \(n\) is a pair \((i,\sigma)\) where \(1 \leq i \leq n+1\) and \(\sigma\) is a state of \({\cal P}\).
If \(s = (i, \sigma)\) is a snapshot of \({\cal P}\) and \(V\) is a variable of \({\cal P}\), then the value of \(V\) at \(s\) means the value of \(V\) at \(\sigma\).
A snapshot \((i,\sigma)\) of a program \({\cal P}\) is called terminal if \(i = n+1\).
If \((i,\sigma)\) is a nonterminal snapshot of \({\cal P}\), the successor of \((i,\sigma)\) is defined to be the snapshot \((j,\tau)\) given by the following table:
| \(i\)th instruction | successor |
|---|---|
| \(V \leftarrow V\) | \((j,\tau) = (i+1, \sigma)\) |
| \(V \leftarrow V+1\) \(\sigma\) contains \(V = m\) |
\((j,\tau) = (i+1, \sigma')\) where \(\sigma'\) is obtained from \(\sigma\) by replacing \(V = m\) with \(V = m+1\) |
| \(V \leftarrow V~\dot{-}~1\) \(\sigma\) contains \(V = m\) |
\((j,\tau) = (i+1, \sigma')\) where \(\sigma'\) is obtained from \(\sigma\) by replacing \(V = m\) with \(V = m~\dot{-}~1\) |
| \(\textbf{if } V \neq 0 \textbf{ goto } L\) |
\((j,\tau) = \left\{
\begin{array}{ll}
(i+1, \sigma) & \text{ if } \sigma \text{ contains } V = 0 \\
(j', \sigma) & \text{ otherwise }
\end{array}\right.\) where \(j'\) is the least natural number such that the \(j'\)th instruction of \({\cal P}\) is labelled \(L\). |
A computation of a program \({\cal P}\) is defined to be a sequence (i.e. a list) \(s_1,\ldots,s_k\) of snapshots of \({\cal P}\) such that \(s_{i+1}\) is the successor of \(s_i\) for \(i =1,\ldots,k\) and \(s_k\) is terminal.
Let \({\cal P}\) be any program in the language \({\cal S}\).
Let \(r_1,\ldots,r_m\) be \(m\) given natural numbers.
The initial state \(\sigma\) consists of the equations \[Y=0,~~~ X_1 = r_1,~~\ldots,~~X_m = r_m,\] and the equations \[ V= 0\] for each variable \(V\) in \({\cal P}\) other than \(Y,X_1,\ldots,X_m\).
The snapshot \((1,\sigma)\) is the initial snapshot.
Define \(\psi_{\cal P}^{(m)}(r_1,\ldots,r_m)\) to be the value of \(Y\) at the terminal snapshot if there is a computation of \({\cal P}\) beginning with the initial snapshot; else \(\psi_{\cal P}^{(m)}(r_1,\ldots,r_m)\) is undefined and we write \(\psi_{\cal P}^{(m)}(r_1,\ldots,r_m) \uparrow\).
Let \({\cal P}\) denote the program in the example above. The following list of snapshots is a computation of \({\cal P}\): \begin{eqnarray*} (1, \{X=2, Y = 0, Z = 0 \}), \\ (4, \{X=2, Y = 0, Z = 0 \}), \\ (5, \{X=1, Y = 0, Z = 0 \}), \\ (6, \{X=1, Y = 1, Z = 0 \}), \\ (7, \{X=1, Y = 1, Z = 1 \}), \\ (1, \{X=1, Y = 1, Z = 1 \}), \\ (4, \{X=1, Y = 1, Z = 1 \}), \\ (5, \{X=0, Y = 1, Z = 1 \}), \\ (6, \{X=0, Y = 2, Z = 1 \}), \\ (7, \{X=0, Y = 2, Z = 2 \}), \\ (1, \{X=0, Y = 2, Z = 2 \}), \\ (2, \{X=0, Y = 2, Z = 3 \}), \\ (3, \{X=0, Y = 2, Z = 3 \}), \\ (8, \{X=0, Y = 2, Z = 3 \}). \end{eqnarray*}
Thus, \(\psi_{\cal P}^{(1)}(2) = 2.\) In fact, it can be seen that \(\psi_{\cal P}^{(1)}(x) = x\) for all \(x \in \mathbb{N}\).
Now let \({\cal P}\) denote the program: \[ \begin{array}{ll} [A] & X \leftarrow X + 1 \\ & \textbf{if } X \neq 0 \textbf{ goto } A \end{array} \] Note that for any initial snapshot, there is no computation. Hence, for all \(r \in \mathbb{N}\), we have \(\psi_{\cal P}^{(1)}(r) \uparrow\).
Each program is permitted to be used with any number of inputs.
If the program has \(n\) input variables but only \(m \lt n\) are specified, the remaining input variables are assigned the value 0 and the computation proceeds.
If \(m\) values are specified where \(m \gt n\), the extra input values are ignored.
For any program \({\cal P}\) and any positive integer \(m\), the function \[\psi_{\cal P}^{(m)}(x_1,\ldots,x_m)\] is said to be computed by \({\cal P}\).
A given partial function \(g\) is said to be partially computable (partial recursive) if it is computed by some program; i.e. there exists a program \({\cal P}\) such that for all \(r_1,\ldots,r_m \in \mathbb{N}\), \(g(r_1,\ldots,r_m)\) is defined if and only if \(\psi_{\cal P}^{(m)}(r_1,\ldots,r_m)\) is and \[g(r_1,\ldots,r_m) = \psi_{\cal P}^{(m)}(r_1,\ldots,r_m)\] whenever \(\psi_{\cal P}^{(m)}(r_1,\ldots,r_m)\) is defined.
\(g\) is said to be computable (recursive, or general recursive) if it is total.
A predicate is said to be computable (or decidable) if it is computable as a Boolean-valued function.