(Notes from Chapter 2, Section 5)
We are going to augment our programming language by introduction the following macros:
\(\textbf{goto } L\)
This is an unconditional jump to the label \(L\). It can be realized as \[\begin{array}{ll} & Z \leftarrow Z+1 \\ & \textbf{if } Z \neq 0 \textbf{ goto } L \end{array}\] where \(Z\) is a local variable that does not appear anywhere else in the program.
\(W \leftarrow f(V_1,\ldots, V_n)\)
This macro assigns to \(W\) the value of the \(n\)-ary function \(f\) evaluated at the values of \(V_1,\ldots,V_n\). Details on expanding this macro are given later.
\(\textbf{if } P(V_1,\ldots,V_n) \textbf{ goto } L\)
Here, \(P\) is a computable predicate. The expansion of the above is \[ \begin{array}{l} & Z \leftarrow P(V_1,\ldots,V_n) \\ & \textbf{if } Z \neq 0 \textbf{ goto } L \end{array} \] Note that when the macro \(\textbf{if } P(V_1,\ldots,V_n) \textbf{ goto } L\) is expanded in a program, we must choose a variable \(Z\) that does not appear in the rest of the program.
We first look at the simpler macro \(W \leftarrow Z\) which copies the value of \(Z\) to \(W\). Suppose that it occurs in some program \({\cal P}\). Let \(Z'\) be a local variable that does not appear anywhere in \({\cal P}\). The following will do: \[ \begin{array}{ll} [A] & W \leftarrow W~\dot{-}~1 \\ & \textbf{if } W \neq 0 \textbf{ goto } A \\ [B] & \textbf{if } Z \neq 0 \textbf{ goto } C \\ & \textbf{goto } D_1 \\ [C] & Z \leftarrow Z~\dot{-}~1 \\ & Z' \leftarrow Z' + 1 \\ & W \leftarrow W + 1 \\ & \textbf{goto } B \\ [D_1] & \textbf{if } Z' \neq 0 \textbf{ goto } D_2 \\ & \textbf{goto } E \\ [D_2] & Z' \leftarrow Z'~\dot{-}~1 \\ & Z \leftarrow Z + 1 \\ & \textbf{goto } D_1 \end{array} \] The first two lines set \(W\) to \(0\). Lines three to six copy the value of \(Z\) over to \(W\) and \(Z'\). Once that is done, the jump to \(D_1\) starts the process of restoring the value of \(Z\) from \(Z'\).
To expand \(W \leftarrow f(V_1,\ldots, V_n)\) in a program \({\cal P}\), let \({\cal Q}\) be a program that computes \(f\) that uses \(k\) local variables. Assume that the input variables in \({\cal Q}\) are \(X_1,\ldots, X_n\). Rename these input variables from \(X_1,X_2,\ldots \) to \(Z_{m+1},Z_{m+2},\ldots\) where \(m\) is the least integer for which no local variable \(Z_i\) appears in \({\cal P}\) for \(i \geq m\). Rename the local variables in \({\cal Q}\) to \(Z_{m+n+1},\ldots, Z_{m+n+k}\). Rename the output variable in \({\cal Q}\) to \(Z_m\). Finally, rename the labels in \({\cal Q}\) to labels that do not appear in \({\cal P}\).
Then the macro can be expanded as \[\begin{array}{ll} & Z_m \leftarrow 0 \\ & Z_{m+1} \leftarrow V_1 \\ & \vdots \\ & Z_{m+n} \leftarrow V_n \\ & Z_{m+n+1} \leftarrow 0 \\ & \vdots \\ & Z_{m+n+k} \leftarrow 0 \\ & {\cal Q} \\ & W \leftarrow Z_m \end{array}\]
Clearly, if \(f(V_1,\ldots,V_n)\) is undefined, the program \({\cal Q}\) will not terminate, thus making \({\cal P}\) not terminate as well.