(Notes from Chapter 6, Sections 1 and 2)
The symbols \(q_1,q_2,q_3,\ldots\) represent states.
\(s_0,s_1,s_2,\ldots\) represent symbols that can appear on the tape where \(s_0 = B\) is the “blank”.
A quadruple is one of the following:
\(\begin{array}{llll} q_i & s_j & s_k & q_l \end{array}\), signifying that in state \(q_i\) scanning symbol \(s_j\), the device prints \(s_k\) and goes into state \(q_l\).
\(\begin{array}{llll} q_i & s_j & R & q_l \end{array}\), signifying that in state \(q_i\) scanning symbol \(s_j\), the device moves one square to the right and goes into state \(q_l\)
\(\begin{array}{llll} q_i & s_j & L & q_l \end{array}\), signifying that in state \(q_i\) scanning symbol \(s_j\), the device moves one square to the left and goes into state \(q_l\)
A Turing machine is a set of quadruples, no two of which begin with the same pair \(q_is_j\). Any finite set of quadruples is called a nondeterministic Turing machine.
The alphabet of a given Turing machine \({\cal M}\) consists of all the symbols \(s_j\) which appear in quadruples of \({\cal M}\) except \(s_0\).
A Turing machine always begins in state \(q_1\).
A Turing machine halts if it is in state \(q_i\) scanning \(s_j\) and there is no quadruple of the machine beginning with \(q_is_j\).
Let \(f(x_1,\ldots,x_m)\) be an \(m\)-ary partial function on \(A^*\) for a given alphabet \(A\). Then the Turing machine \({\cal M}\) 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 & q_1 & \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 those in \(A\).
We say that \({\cal M}\) computes \(f\) strictly if:
the alphabet of \({\cal M}\) is a subset of \(A\);
whenever \({\cal M}\) halts, the ifnal tape configuraton has the form \[ \begin{array}{cccccccc} B & y \\ \uparrow \\ q_i & \end{array} \] where the \(y\) contains no blanks.
Theorem 1.1. Any partial function that can be computed by a Post-Turing program can be computed by a Turing machine using the same alphabet.
Using Corollary 6.4 from Chapter 5, Theorem 1.1 can be strengthened to
Theorem 1.2. Let \(f\) be an \(m\)-ary partially computable function on \(A^*\) for a given alphabet \(A\). Then there is a Turing machine \({\cal M}\) that computes \(f\) strictly.It is interesting to apply Theorem 1.2 to the case \(A = \{1\}\). Thus, if \(f(x_1,\ldots,x_m)\) is any partially computable function on \(\mathbb{N}\), then there is a Turing machine that computes \(f\) using only the symbols \(B\) and \(1\). The initial tape configuration corresponding to the inputs \(x_1,\ldots,x_m\) is \[ \begin{array}{llllll} B & 1^{[x_1]} & B & \cdots & B & 1^{[x_m]} \\ \uparrow \\ q_1 \end{array} \] and the final configuration when \(f(x_1,\ldots,x_m)\downarrow\) will be \[ \begin{array}{llllll} B & 1^{[f(x_1,\ldots,x_m)]} \\ \uparrow \\ q_{K+1} \end{array} \] for some state \(q_{K+1}\) such that no quadruple begins \(q_{K+1} B\).
A quintuple is one of the following:
\(\begin{array}{lllll} q_i & s_j & s_k & R & q_l \end{array}\), signifying that in state \(q_i\) scanning symbol \(s_j\), the device prints \(s_k\) and then moves one square to the right and goes into state \(q_l\).
\(\begin{array}{lllll} q_i & s_j & s_k & L & q_l \end{array}\), signifying that in state \(q_i\) scanning symbol \(s_j\), the device prints \(s_k\) and then moves one square to the left and goes into state \(q_l\).
Theorem 1.3. Any partial function that can be computed by a (quadruple) Turing machine can be computed by a quintuple Turing machine using the same alphabet.
Theorem 1.4. Any partial function that can be computed by a quintuple Turing machine can be computed by a Post-Turing program using the same alphabet.
Corollary 1.5. For a given partial function \(f\), the following are equivalent:
\(f\) can be computed by a Post-Turing program;
\(f\) can be computed by a Turing machine;
\(f\) can be computed by a quintuple Turing machine.
Proof.
\(1 \Rightarrow 2\): Theorem 1.1.
\(2 \Rightarrow 3\): Theorem 1.3.
\(3 \Rightarrow 1\): Theorem 1.4.
Recall that if \(g(x)\) is a partially computable function of one variable, then \(g(x) = \Phi(x,z_0)\) where \(z_0\) is the number of a program in the language \({\cal S}\) that computes \(g\). Let \({\cal M}\) be a Turing machine that computes \(\Phi(x,z)\) with alphabet \(\{1\}\). Then beginning with the configuration \[ \begin{array}{llllll} B & 1^{[x]} & B & 1^{[z_0]} \\ \uparrow \\ q_1 \end{array} \] \({\cal M}\) will compute \(\Phi(x,z_0)\), i.e. \(g(x)\).
Thus, \({\cal M}\) can be used to compute any partially computable function of one variable. We call \({\cal M}\) a universal Turing machine.