(Notes from Chapter 5, Sections 4 and 5)
\({\cal T}\) denotes the Post-Turing programming language for computing string functions on the alphabet \(A = \{s_1,\ldots,s_n\}\) with an additional symbol \(s_0\) called the blank. (The blank is often written as \(B\).).
No variables. Information processed is placed on one linear tape infinite in both directions. The tape is ruled into squares each of which can carry a single symbol. At any given time, all but a finite number of squares on the tape are blank. Each step of a computation is sensitive to the symbol on the square being “scanned”. The following table specifies the language:
| Instruction | Interpretation |
|---|---|
| \(\textbf{print } \sigma\) | Replace the symbol on the square being scanned by \(\sigma\) |
| \(\textbf{if } \sigma \textbf{ goto } L\) | go to the first instruction labeled \(L\) if the symbol currently scanned is \(\sigma\); otherwise, continue to the next instruction. |
| \(\textbf{right}\) | Scan the square immediately to the right of the square presently scanned. |
| \(\textbf{left}\) | Scan the square immediately to the left of the square presently scanned. |
Since the tape is infinite, when we show the tape, we show only the section that contains all of the nonblank squares. This section is finite because we assume that only finitely many squares are nonblank at any given time. The square currently being scanned is indicated by an arrow pointing up, just below the scanned square. For example, \[ \begin{array}{ccccc} s_1 & s_2 & B & s_2 & s_1 \\ & & & \uparrow & \end{array} \] indicates that the tape consists of \(s_1s_2B s_2s_1\) with blank squares to the left and right, and that the square currently scanned contains the \(s_2\) furthest to the right.
A tape configuration consists of the tape contents together with a specification of one square as being currently scanned.
To compute a partial function \(f(x_1,\ldots,x_m)\) of \(m\) variables on \(A^*\), we use the initial tape configuration: \[ \begin{array}{ccccccc} B & x_1 & B & x_2 & \cdots & B & x_m \\ \uparrow & \end{array} \] For example, with \(n = 2\), \(x_1 = s_1 s_2\), \(x_2 = s_2s_1\), \(x_3=0\), the initial tape configuration is \[ \begin{array}{ccccccc} B & s_1 & s_2 & B & s_2 & s_1 & B \\ \uparrow & \end{array} \] Note that there is no way to distinguish this from that for which there are only two inputs \(x_1 = s_1 s_2\) and \(x_2 = s_2 s_1\). Thus, the number of arguments must be provided externally.
Consider the following Post-Turing program with the alphabet \(\{s_1,s_2,s_3\}\): \[ \begin{array}{ll} [A] & \textbf{right} \\ & \textbf{if } s_1\textbf{ goto } A \\ & \textbf{if } s_2\textbf{ goto } A \\ & \textbf{if } s_3\textbf{ goto } A \\ & \textbf{print } s_1 \\ & \textbf{right} \\ & \textbf{print } s_1 \\ [C] & \textbf{left} \\ & \textbf{if } s_1\textbf{ goto } C \\ & \textbf{if } s_2\textbf{ goto } C \\ & \textbf{if } s_3\textbf{ goto } C \\ \end{array} \] It begins with a tape configuration \[ \begin{array}{ccccccc} B & x \\ \uparrow & \end{array} \] and halts with the tape configuration \[ \begin{array}{ccccccc} B & x & s_1 & s_1. \\ \uparrow & \end{array} \]
Let \(f(x_1,\ldots,x_m)\) be an \(m\)-ary partial function on the alphabet \(\{s_1,\ldots,s_n\}\). Then the program \({\cal P}\) in the Post-Turing language \({\cal T}\) is said to compute \(f\) if when started in the tape configuration \[ \begin{array}{ccccccc} B & x_1 & B & x_2 & \cdots & B & x_m \\ \uparrow & \end{array} \] it eventually halts if and only if \(f(x_1,\ldots,x_m)\) is defined and if, on halting, the string \(f(x_1,\ldots,x_m)\) can be read off the tape by ignoring all symbols other than \(s_1,\ldots,s_n\). (Note that we permit \({\cal P}\) to contain instructions that mention symbols other than \(s_1,\ldots,s_n\).)
The program \({\cal P}\) is said to compute \(f\) strictly if two addtional conditions are met:
no instruction in \({\cal P}\) mentions any symbol other than \(s_0,s_1,\ldots,s_n\);
whenever \({\cal P}\) halts, the tape configuraton is of the form \[ \begin{array}{cccccccc} \cdots & B & B & y & B& B & \cdots, \\ & & \uparrow & \end{array} \] where the string \(y\) contains no blanks.
Theorem 5.1. If \(f(x_1,\ldots,x_n)\) is partially computable in \({\cal S}_n\), then there is a Post-Turing program that computes \(f\) strictly.
Key ingredients of proof. The key is to show that if \({\cal P}\) is a program in \({\cal S}_n\) that computes \(f\), a program \({\cal Q}\) simulating \({\cal P}\) can be constructed.
We assume that \({\cal P}\) uses \(l := m+k+1\) variables: \[X_1,\ldots,X_m,Z_1,\ldots,Z_k,Y.\] These variables are written, in the same order, as \[V_1,\ldots,V_l.\]
Our scheme is to maintain at the beginning of each simulated step the following tape configuration: \[\begin{array}{llllllllllllllllllll} B&x_1&B & \cdots & B&x_m&B& z_1 & B &\cdots&B&z_k&B&y, \\ \uparrow \end{array}\] where \(x_1,\ldots,x_m,z_1,\ldots,z_k,y\) are the current values computed for the corresponding variables. Note that the initial tape configuration \[\begin{array}{llllllllllllllllllll} B&x_1&B & \cdots & B&x_m \\ \uparrow \end{array}\] is already in the correct form since the remaining variables are initialized to be 0.
After all steps have been simulated, one can simply erase \(x_1,\ldots,x_m,z_1,\ldots,z_k\) with \(B\) to give the tape configuration \[\begin{array}{llllllllllllllllllll} \cdots & B&B &B&y &B & B & \cdots\\ & & & \uparrow \end{array}\]