Up

(Notes from Chapter 5, Section 6 and some from Section 1)

Simulation of \({\cal T}\) in \({\cal S}\)

Theorem 6.1. If there is a Post-Turing program that computes the partial function \(f(x_1,\ldots,x_n)\), then \(f\) is partially computable.

With the above theorem, we have another important result of this course:

Theorem 6.2. Let \(f\) be an \(m\)-ary partial function on \(A^*\), where \(A\) is an alphabet of \(n\) symbols. Then the following conditions are equivalent:

  1. \(f\) is partially computable;

  2. \(f\) is partially computable in \({\cal S}_n\);

  3. \(f\) is computed strictly by a Post-Turing program;

  4. \(f\) is computed by a Post-Turing program.

Proof.

(1) \(\Rightarrow\) (2): Theorem 3.2.

(2) \(\Rightarrow\) (3): Theorem 5.2.

(3) \(\Rightarrow\) (4): Obvious.

(4) \(\Rightarrow\) (3): Theorem 6.1.

Corollary 6.3. For any \(n, l\geq 1\), an \(m\)-ary partial function \(f\) on \(\mathbb{N}\) is partially computable in \({\cal S}_n\) if and only if it is also partially computable in \({\cal S}_l\).

Corollary 6.4. Every partially computable function is computed strictly by some Post-Turing program that uses only the symbols \(s_0, s_1\).

Proof of Theorem 6.1

Let \({\cal P}\) be a Post-Turing program that computes \(f\). We will show how a program \({\cal Q}\) in the language \({\cal S}\) computing \(f\) can be constructed.

Suppose that \(f\) is an \(m\)-ary function on \(A^*\) where \(A = \{s_1,\ldots,s_n\}\). We write the symbols used by \({\cal P}\) in the order \[s_1,\ldots,s_n,s_{n+1},\ldots,s_r,B.\] Note that \(s_{n+1},\ldots,s_r\) are symbols used by \(P\) that are not in the alphabet and the blank is regarded as the symbol \(s_{r+1}\). (We do not assume \({\cal P}\) computes \(f\) strictly.)

The program \({\cal Q}\) will work with three numbers \(L,H,R\) that encode the tape configuration as follows:

Even though the string to the left (or right) of the head is an infinite string, only finitely many symbols are not blank. Hence, we just need to encode finite strings that occur around the head.

For example, suppose that the tape configuration is \[ \begin{array}{ccccccccccc} \cdots & B & B & s_1 & s_2 & B & s_2 & M & B & B & \cdots \\ & & & & \uparrow & \end{array} \] where \(M\) is the only symbol used by \(P\) not in the alphabet \(A\). Then \(r = 3\) with \(s_3 = M\) and \(s_4 = B\). Thus, \[ H = 2. \] We could have \[L = 1\] representing the string \(s_1\) or \[L = 4\cdot 4 +1 = 17\] representing the string \(B s_1\). Hence, \(L\) could represent a string containing any number of blanks to the left as long as there is no nonblank further to the left.

Similarly, we could have \[R = 4\cdot 4^2 + 2 \cdot 4 + 3\] representing the string \(Bs_2 M\) or \[R = 4\cdot 4^4 + 2 \cdot 4^3 + 3\cdot 4^2 + 4\cdot 4 + 4\] representing the string \(Bs_2 MBB\).

With the above encodings, we see that the input strings must be converted to numbers in base \(r+1\): \[\begin{array}{l} L \leftarrow r+1 \\ H \leftarrow r+1 \\ Z_1 \leftarrow \textbf{upchange}_{n,r+1}(X_1) \\ Z_2 \leftarrow \textbf{upchange}_{n,r+1}(X_2) \\ \vdots \\ Z_m \leftarrow \textbf{upchange}_{n,r+1}(X_m) \\ R \leftarrow \textbf{concat}_{r+1} (Z_1,r+1,Z_2,r+1,\ldots,r+1,Z_m) \end{array} \] The above program fragment will go at the beginning of \({\cal Q}\).

The output computed by \({\cal P}\), which is obtained from what is on the tape by removing all the blanks, can be extracted by the following: \[\begin{array}{l} Z \leftarrow \textbf{concat}_{r+1}(L,H,R) \\ Y \leftarrow \textbf{downchange}_{n,r+1}(Z) \\ \end{array} \] The above program fragment will go at the end of \({\cal Q}\).

We now show how each instruction in \({\cal P}\) can be simulated.