Equivalence of the models

We have met five definitions of computable partial function. Some equivalences are already proved:

• WHILE-computable $\iff$ partial recursive (Theorem 9.6);
• partial recursive $\iff$ λ-definable (Theorem 11.7 and Theorem 11.8);
• WHILE-computable $\implies$ URM-computable (Proposition 9.8); the converse follows from the other implications below, and is also the last exercise of the lesson on WHILE programs.

It remains to connect Turing machines to the other models. In this lesson we prove that every Turing-computable function is partial recursive, by arithmetizing the computations of Turing machines, and that every URM-computable function is Turing-computable, by simulation. Along the way we obtain Kleene’s normal form theorem and a universal partial recursive function.

Theorem 12.1 (Equivalence of the models).#

For a partial function $f : \nat^k \rightharpoonup \nat$, the following are equivalent:

1. $f$ is Turing-computable;
2. $f$ is URM-computable;
3. $f$ is WHILE-computable;
4. $f$ is partial recursive;
5. $f$ is λ-definable.

12.1 Arithmetization of Turing machines

Fix a Turing machine $M$. Without loss of generality its states are $0, 1, \dots, m$ with initial state $0$ and halting state $1$, and its alphabet is $\{0, 1, \dots, a\}$, where $0$ stands for the blank $\sqcup$ and $1$ for the symbol $1$. We use the sequence coding $[\ldots]$ of the lesson Coding finite sequences, with the primitive recursive operations $\mathrm{lh}$, $(s)'_i$, concatenation $*$, and

• $\mathrm{cons}(b, s) = [b] * s$, which adds $b$ in front of $s$;
• $\mathrm{hd}(s) = (s)'_0$ if $\mathrm{lh}(s) > 0$, and $0$ otherwise;
• $\mathrm{tl}(s) = [(s)'_1, \dots, (s)'_{\mathrm{lh}(s) - 1}]$ if $\mathrm{lh}(s) > 0$, and $[\,]$ otherwise.

These are primitive recursive; for instance $\mathrm{tl}(s) = \prod_{i + 1 < \mathrm{lh}(s)} p_i^{(s)_{i+1}}$.

Coding configurations. A configuration $(q, \tau, h)$ is coded by a triple $\langle q, \ell, r \rangle$ where $r$ is the code of the sequence $\tau(h), \tau(h+1), \dots, \tau(h + j)$ and $\ell$ is the code of $\tau(h-1), \tau(h-2), \dots, \tau(h - i)$, for some $i, j$ large enough that all non-blank cells are covered. The left part is stored in reverse order, so that the cells adjacent to the head are at the front of both sequences. Several codes represent the same configuration, differing by trailing blanks; this causes no problem, since all functions below treat a missing cell as a blank, via $\mathrm{hd}$.

One step. Define $\mathrm{Next}(c)$ for $c = \langle q, \ell, r \rangle$ as follows. If $q = 1$ (halting), $\mathrm{Next}(c) = c$. Otherwise let $b = \mathrm{hd}(r)$ be the scanned symbol and $\delta(q, b) = (q', b', D)$. Then

$$\mathrm{Next}(c) = \begin{cases} \langle q',\ \mathrm{cons}(b', \ell),\ \mathrm{tl}(r) \rangle & \text{if } D = R, \\ \langle q',\ \mathrm{tl}(\ell),\ \mathrm{cons}(\mathrm{hd}(\ell),\ \mathrm{cons}(b', \mathrm{tl}(r))) \rangle & \text{if } D = L. \end{cases}$$

This is a definition by cases over the finitely many pairs $(q, b)$, plus one case for symbols $b$ out of range. Hence $\mathrm{Next}$ is primitive recursive.

Iteration. Let $\mathrm{Init}(\vec x) = \langle 0, [\,], w_{\vec x} \rangle$, where $w_{\vec x}$ is the code of the word $1^{x_1 + 1}\, 0\, 1^{x_2 + 1}\, 0 \cdots 0\, 1^{x_k + 1}$; it is primitive recursive (for instance as a concatenation of codes of constant sequences, computed by bounded products). Define by primitive recursion

$$\begin{gathered} \mathrm{Conf}(\vec x, 0) = \mathrm{Init}(\vec x), \\ \mathrm{Conf}(\vec x, t + 1) = \mathrm{Next}(\mathrm{Conf}(\vec x, t)). \end{gathered}$$

Then $\mathrm{Conf}(\vec x, t)$ codes the configuration after $t$ steps if $M$ has not halted before step $t$, and the halting configuration otherwise — this is why $\mathrm{Next}$ fixes halting configurations.

Halting and output. The predicates $\mathrm{Halt}(c) \iff \pi_0(c) = 1$ (where $\pi_0$ extracts the state from the triple) and $\mathrm{Std}(c)$: “every entry of $\ell$ is $0$, and $r$ consists of $y + 1$ entries equal to $1$ followed only by $0$s, for some $y$” are primitive recursive, by bounded quantification over the indices of $\ell$ and $r$. The output $\mathrm{Out}(c)$, the number of leading $1$s of $r$ minus one, is primitive recursive by bounded minimization.

Proposition 12.2.#

Every Turing-computable partial function is partial recursive.

Proof of Proposition 12.2.

Let $M$ compute $f$. Let $t_0(\vec x) \simeq \mu t\, \mathrm{Halt}(\mathrm{Conf}(\vec x, t))$ and $c(\vec x) \simeq \mathrm{Conf}(\vec x, t_0(\vec x))$, the final configuration. Then

$$f(\vec x) \simeq \mathrm{Out}(c(\vec x)) + 0 \cdot \mu z\, [\chi_{\mathrm{Std}}(c(\vec x)) = 1].$$

If $M$ does not halt, $t_0(\vec x)\diverge$. If it halts in a non-standard configuration, the second summand is a search which never succeeds, so the expression diverges — here we use the convention that $0 \cdot e$ is undefined when $e$ is. If it halts in a standard configuration, the second summand is $0$ and the value is the output. All functions involved are primitive recursive, except for the two minimizations.

12.2 Kleene’s normal form theorem

The construction above depends on the machine $M$ only through its transition table, a finite object. Code each machine by an integer $e$, say $e = [m, a, d]$ where $d$ codes the list of the transitions $\delta(q, b) = (q', b', D)$ as quintuples. Integers which do not code a machine are treated as coding a fixed machine that never halts. Then the step function $\mathrm{Next}(e, c)$ is primitive recursive in both arguments: the transition is found by a bounded search in the list $d$.

Theorem 12.3 (Kleene’s normal form).#

For each $k \geq 1$ there are a primitive recursive predicate $T_k(e, \vec x, s)$ and a primitive recursive function $U(s)$ such that:

1. for every $e$ and $\vec x$, there is at most one $s$ with $T_k(e, \vec x, s)$;
2. for every Turing machine with code $e$, the function it computes is $\vec x \mapsto U(\mu s\, T_k(e, \vec x, s))$.

Consequently every partial recursive function $f$ can be written $f(\vec x) \simeq U(\mu s\, T_k(e, \vec x, s))$ for some $e$.

Proof of Theorem 12.3.

Let $T_k(e, \vec x, s)$ state that $s$ codes the whole computation: $s = [c_0, \dots, c_t]$ with $c_0 = \mathrm{Init}(\vec x)$, $c_{i+1} = \mathrm{Next}(e, c_i)$ for $i < t$, $c_t$ halting and standard, and $c_i$ not halting for $i < t$. This is a conjunction of bounded quantifications over $i < \mathrm{lh}(s)$, hence primitive recursive. Such an $s$ is unique: $c_0$ is fixed, each $c_{i+1}$ is determined by $c_i$, and $t$ is the first index of a halting configuration. Let $U(s) = \mathrm{Out}((s)'_{\mathrm{lh}(s) - 1})$, the output read on the last configuration.

If the machine $e$ halts on $\vec x$ in a standard configuration, $\mu s\, T_k(e, \vec x, s)$ is the code of its computation and $U$ returns the output. Otherwise no $s$ satisfies $T_k$, and the search diverges. The last statement follows once we know that every partial recursive function is Turing-computable. This is the chain of implications (4) ⇒ (3) ⇒ (2) ⇒ (1) of the last section, whose proof does not use the normal form theorem.

12.3 From register machines to Turing machines

Proposition 12.4.#

Every URM-computable partial function is Turing-computable.

Proof of Proposition 12.4.

Let $P = I_1, \dots, I_s$ compute $f : \nat^k \rightharpoonup \nat$, and let $\rho = \max(\rho(P), k)$. We build a multi-tape Turing machine $N$ with $\rho + 1$ tapes, following the conventions of Definition 3.5: tape $1$ holds the input and output, and tape $n + 1$, for $1 \leq n \leq \rho$, holds the content of $R_n$ in unary, as $\ulcorner R_n \urcorner$ starting at the head position. The index of the current instruction is stored in the finite control of $N$.

1. Initialization. $N$ reads the input $\ulcorner x_1 \urcorner \sqcup \cdots \sqcup \ulcorner x_k \urcorner$ on tape $1$ and copies the $n$-th block to tape $n + 1$; the other register tapes receive $\ulcorner 0 \urcorner$.

2. Simulation. For each instruction, $N$ has a group of states:

   • $Z(n)$: erase tape $n + 1$ and write a single $1$;
   • $S(n)$: append a $1$ at the end of the block on tape $n + 1$, and return;
   • $T(m, n)$: erase tape $n + 1$ and copy the block of tape $m + 1$ onto it;
   • $J(m, n, q)$: scan the blocks of tapes $m + 1$ and $n + 1$ simultaneously from left to right; they have equal length iff both heads reach a blank at the same time. Return the heads, and enter the group of instruction $q$ or $i + 1$ accordingly.

   When the current index exceeds $s$, the simulation ends.

3. Output. $N$ erases tape $1$, copies the block of tape $2$ (the register $R_1$) onto it, and halts with head $1$ on its first cell.

By induction on the number of steps of $P$, after the simulation of $j$ instructions, the tapes of $N$ represent the registers of $P$ after $j$ steps. Hence $N$ computes $f$. By Theorem 3.6, so does some single-tape machine.

12.4 Proof of the equivalence

We can now complete the proof of Theorem 12.1. The following implications are established:

$$(1) \Longrightarrow (4) \Longrightarrow (3) \Longrightarrow (2) \Longrightarrow (1), \qquad (4) \Longleftrightarrow (5).$$

Indeed, (1) ⇒ (4) is Proposition 12.2; (4) ⇒ (3) is Theorem 9.6; (3) ⇒ (2) is Proposition 9.8; (2) ⇒ (1) is Proposition 12.4; and (4) ⇔ (5) was proved in the previous lesson. All five classes coincide.

From now on, we call these functions the partial computable functions, and their total members the computable functions.

12.5 The universal function

A consequence of the normal form theorem is that a single partial computable function evaluates all the others.

Corollary 12.5 (Universal function).#

The function $\Phi(e, \vec x) \simeq U(\mu s\, T_k(e, \vec x, s))$ is partial computable, and for every partial computable $f : \nat^k \rightharpoonup \nat$ there is $e$ with $f(\vec x) \simeq \Phi(e, \vec x)$ for all $\vec x$. In particular, there is a universal Turing machine, which on input $(e, \vec x)$ simulates the machine coded by $e$ on $\vec x$.

Proof of Corollary 12.5.

$\Phi$ is partial recursive, as it is obtained from primitive recursive functions by one minimization and one composition. By the equivalence, it is computed by some Turing machine. The second statement is Theorem 12.3.

Writing $\Phi_e(\vec x) \simeq \Phi(e, \vec x)$, the sequence $\Phi_0, \Phi_1, \Phi_2, \dots$ is an enumeration of all partial computable functions. Its study is the subject of the course on the fundamentals of computability, starting with the lesson Programs as numbers.

12.6 Exercises

Exercise 12.6 ★.

Show that the function $\mathrm{Init}(\vec x)$ is primitive recursive.

Solution

For a single argument, the code of $1^{x+1}$ is $\prod_{i \leq x} p_i^{2}$ (each entry $1$ is coded by exponent $2$), a bounded product. The code of a separator $[0]$ is $2$. The code of the whole word is obtained by concatenating these codes with the primitive recursive operation $*$, and $\mathrm{Init}(\vec x) = \langle 0, 1, w_{\vec x} \rangle$, where $1 = [\,]$.

Exercise 12.7 ★★.

Using the uniform step function of the normal form theorem, show that the predicate $H(e, x, t)$: “the machine of code $e$ halts on input $x$ within $t$ steps, in a standard final configuration” is primitive recursive, and that $\{(e, x) : \exists t\ H(e, x, t)\}$ is the domain of the universal function.

Solution

Let $\mathrm{Conf}(e, x, t)$ be the uniform version of the iteration function, defined by primitive recursion from $\mathrm{Next}(e, c)$, hence primitive recursive in $e, x, t$. Since $\mathrm{Next}$ fixes halting configurations, $H(e, x, t) \iff \mathrm{Halt}(\mathrm{Conf}(e, x, t)) \wedge \mathrm{Std}(\mathrm{Conf}(e, x, t))$, a primitive recursive predicate. The machine halts on $x$ in a standard configuration iff some $t$ satisfies $H$, iff some $s$ satisfies $T_1(e, x, s)$, iff $\mu s\, T_1(e, x, s)$ converges, iff $(e, x) \in \dom \Phi$ (as $U$ is total).

Exercise 12.8 ★★★.

Show that there is a total computable function $g : \nat^2 \to \nat$ such that the functions $g(e, \cdot)$ are exactly the primitive recursive functions of one argument, and deduce once more that $g$ is not primitive recursive.

Solution

Code derivations of unary primitive recursive functions by integers, mapping non-codes to a fixed derivation of $Z$. Each derivation can be translated computably into a Turing machine computing the same function; let $t(e)$ be the code of the machine obtained from the derivation $e$. Then $g(e, x) = \Phi(t(e), x)$ is computable and total, since primitive recursive functions are total. If $g$ were primitive recursive, so would be $x \mapsto g(x, x) + 1$, which differs from every $g(e, \cdot)$ at $e$.

12.7 Notes and references

Turing sketched in an appendix to his 1936 paper that the λ-definable functions are computable by his machines, and proved the equivalence of the two notions in 1937; Kleene proved the equivalence of λ-definability with general recursiveness in 1936. The predicate $T$ of the normal form theorem is often called Kleene’s $T$-predicate. The arithmetization of computations given here follows the treatment of register and Turing machines in Cutland’s and Odifreddi’s textbooks.

• S. C. Kleene, General recursive functions of natural numbers, Mathematische Annalen 112 (1936), 727–742.
• A. M. Turing, Computability and λ-definability, Journal of Symbolic Logic 2 (1937), 153–163.
• N. Cutland, Computability: An Introduction to Recursive Function Theory, Cambridge University Press, 1980.
• P. Odifreddi, Classical Recursion Theory, North-Holland, 1989, chapter I.