The universal function and the SMN theorem

Two properties of the enumeration $(\Phi_e)$ make it the right framework for computability theory. The first is that it is itself computable: a single algorithm evaluates $\Phi_e(x)$ from $e$ and $x$. The second is that indices can be manipulated computably: from an index of a function of two arguments and a value $x$ of the first argument, one can compute an index of the function of the second argument obtained by fixing $x$. The first property is the universal function theorem, the second is the SMN theorem. Together they allow one to treat programs as data, which is what the rest of the course does.

2.1 The universal function

Theorem 2.1 (Universal function).#

For every $k \geq 1$, there is an index $u$ such that for all $e$ and $\vec x = (x_1, \dots, x_k)$,

$$\Phi^{(k+1)}_u(e, \vec x) \simeq \Phi^{(k)}_e(\vec x).$$

Proof of Theorem 2.1.

By Universal function, the function $(e, \vec x) \mapsto U(\mu s\ T_k(e, \vec x, s))$ is partial computable. Any of its indices is suitable.

A machine of index $u$ is an interpreter: it receives the code of a machine and an input, decodes the machine, and simulates it step by step. The theorem justifies definitions such as

$$f(x, y) \simeq \Phi_{x+1}(y + 2) \qquad\text{or}\qquad g(e) \simeq \Phi_e(e) + 1,$$

which are partial computable as compositions of the universal function with computable functions. By contrast, no total computable function enumerates the total computable functions (Theorem 6.4 of “Diagonalization and computation”): the universal function is necessarily partial.

2.2 The SMN theorem

Theorem 2.2 (SMN theorem).#

For all $m, n \geq 1$, there is a primitive recursive function $S^m_n : \nat^{m+1} \to \nat$ such that for all $e$, $\vec x = (x_1, \dots, x_m)$ and $\vec y = (y_1, \dots, y_n)$,

$$\Phi^{(n)}_{S^m_n(e, \vec x)}(\vec y) \simeq \Phi^{(m+n)}_e(\vec x, \vec y).$$

The name comes from Kleene’s notation $S^m_n$. The function $S^m_n$ does not run the machine $e$: it transforms its code into the code of another machine, which first writes $\vec x$ on the tape in front of its input, then behaves as the machine $e$. Computing this new code is a finite manipulation of a finite table.

Proof of Theorem 2.2.

We treat $m = n = 1$; the general case is identical, with $m$ blocks to write in front of $n$ blocks. Recall the input convention (Definition 2.4 of “Turing machines”): the input $y$ is the block $\ulcorner y \urcorner = 1^{y+1}$ written from cell $0$, and the input $(x, y)$ is $\ulcorner x \urcorner \sqcup \ulcorner y \urcorner$.

For $x \in \nat$, let $P_x$ be a machine which, started on the tape $\ulcorner y \urcorner$ with the head on cell $0$, halts with the tape $\ulcorner x \urcorner \sqcup \ulcorner y \urcorner$ written from some cell $h$, with the head on cell $h$ and in its halting state. For instance, $P_x$ moves left from cell $0$, writes a blank separator on cell $-1$ (already blank), then writes $x + 1$ ones on the cells $-2, -3, \dots, -x - 2$, moving left after each of them, and finally moves one cell back to the right, halting on cell $h = -x - 2$. This takes $x + O(1)$ states, and the transition table of $P_x$ is obtained from $x$ by a primitive recursive function: it is a fixed table with a chain of $x + 1$ writing states inserted.

Let $M_e$ be the machine of code $e$. The machine $P_x ; M_e$ is obtained by renaming the states of $M_e$ so that they are distinct from those of $P_x$, and by identifying the halting state of $P_x$ with the initial state of $M_e$. Started on $\ulcorner y \urcorner$, it runs $P_x$, reaching the configuration in the initial state of $M_e$ with tape $\ulcorner x \urcorner \sqcup \ulcorner y \urcorner$ written from cell $h$ and head on $h$. This is the initial configuration of $M_e$ on input $(x, y)$, translated by $h$. By Lemma 3.2 of “Programming Turing machines”, the subsequent computation is the translate of the computation of $M_e$ on $(x, y)$: it halts in a standard final configuration with output $z$ if and only if $\Phi^{(2)}_e(x, y)\converge = z$. Hence $P_x ; M_e$ computes $y \mapsto \Phi^{(2)}_e(x, y)$.

Let $S^1_1(e, x)$ be the code of $P_x ; M_e$. Renaming states and merging two tables are operations on finite sequences of integers, and with the coding of machines by sequence codes they are primitive recursive (Proposition 6.2 of “Coding finite sequences”). So $S^1_1$ is primitive recursive.

The SMN theorem is mostly used in the following form, which states that a family of partial computable functions, defined uniformly from a parameter, has indices computable from the parameter.

Corollary 2.3 (Parameter form).#

Let $f : \nat^{1+n} \rightharpoonup \nat$ be partial computable. There is a primitive recursive function $s : \nat \to \nat$ such that for all $x$ and $\vec y$,

$$\Phi^{(n)}_{s(x)}(\vec y) \simeq f(x, \vec y).$$

Proof of Corollary 2.3.

Let $i$ be an index of $f$, and let $s(x) = S^1_n(i, x)$.

In proofs, the corollary is invoked by sentences such as: “for every $x$, let $s(x)$ be an index of the program which, on input $y$, does … (something depending on $x$ and $y$)”, it being understood that the description defines a partial computable function of $(x, y)$, and that $s$ is then total computable. We also say that $s(x)$ is obtained uniformly in $x$.

Example 2.4.#

1. Composition of indices. There is a total computable $c$ with $\Phi_{c(a, b)} = \Phi_a \circ \Phi_b$ for all $a, b$: apply the corollary to $f(\langle a, b \rangle, y) \simeq \Phi_a(\Phi_b(y))$, which is partial computable by the universal function, and compose with the pairing function.
2. Constant functions. There is a total computable $\kappa$ such that $\Phi_{\kappa(x)}$ is the constant function with value $x$.
3. Programs that ignore their input. There is a total computable $z$ such that $\Phi_{z(e, x)}(y) \simeq \Phi_e(x)$ for all $y$: the program $z(e, x)$ ignores its input and runs $\Phi_e$ on $x$. So $\Phi_{z(e, x)}$ is total if $\Phi_e(x)\converge$, and nowhere defined otherwise. This construction is used in many reductions.

2.3 The padding lemma

Every partial computable function has infinitely many indices: adding to a machine states that are never entered does not change what it computes. The indices can moreover be found computably, and above any given bound.

Lemma 2.5 (Padding lemma).#

There is a primitive recursive function $p : \nat^2 \to \nat$ such that for all $e$ and $n$, $p(e, n) \geq n$ and $\Phi^{(k)}_{p(e, n)} = \Phi^{(k)}_e$ for every $k$.

Proof of Lemma 2.5.

Let $M_e$ be the machine of code $e$ (the fixed never-halting machine if $e$ is not a code). For $j \in \nat$, let $M_{e, j}$ be $M_e$ with $j$ additional states, which are never entered and whose transitions are arbitrary, say “write a blank, move right, stay in the same state”. Its computations are those of $M_e$, so it computes the same functions. The machines $M_{e, 0}, M_{e, 1}, \dots$ have different numbers of states, so their codes $c(e, j)$ are pairwise distinct, and $c$ is primitive recursive. Among the $n + 1$ distinct values $c(e, 0), \dots, c(e, n)$, at most $n$ lie below $n$, so one of them is at least $n$. Let $p(e, n) = c(e, j)$ for the least $j \leq n$ with $c(e, j) \geq n$, a bounded search.

Corollary 2.6.#

Every partial computable function has infinitely many indices. Consequently, the set of indices of a given partial computable function is never finite, and for every $e$ the function $n \mapsto p(e, n)$ enumerates infinitely many of the indices of $\Phi_e$.

Proof of Corollary 2.6.

If $f = \Phi_e$, the indices $p(e, n)$, for $n \in \nat$, are unbounded since $p(e, n) \geq n$, hence infinitely many.

2.4 Acceptable numberings

The results of this course depend on the enumeration $(\Phi_e)$ only through a few properties. It is useful to know which ones.

Definition 2.7.#

A numbering of the unary partial computable functions is a sequence $(\psi_e)_{e \in \nat}$ in which every unary partial computable function appears. It is acceptable if

1. the function $(e, x) \mapsto \psi_e(x)$ is partial computable, and
2. there is a total computable $t$ with $\psi_{t(e)} = \Phi_e$ for every $e$.

Proposition 2.8.#

The numbering $(\Phi_e)$ is acceptable. If $(\psi_e)$ is acceptable, there is a total computable $r$ with $\Phi_{r(e)} = \psi_e$ for every $e$, and $(\psi_e)$ satisfies the SMN theorem: there is a total computable $\sigma$ such that $\psi_{\sigma(e, x)}(y) \simeq \psi_e(\langle x, y \rangle)$.

Proof of Proposition 2.8.

For $(\Phi_e)$, take the universal function and $t$ the identity. Let $(\psi_e)$ be acceptable. By Corollary 2.3 applied to $(e, x) \mapsto \psi_e(x)$, there is a total computable $r$ with $\Phi_{r(e)}(x) \simeq \psi_e(x)$. For SMN, apply Corollary 2.3 to $(\langle e, x \rangle, y) \mapsto \psi_e(\langle x, y \rangle)$, giving a total computable $s$ with $\Phi_{s(\langle e, x \rangle)}(y) \simeq \psi_e(\langle x, y \rangle)$, and let $\sigma(e, x) = t(s(\langle e, x \rangle))$.

Rogers proved that any two acceptable numberings differ by a computable permutation of the indices: if $(\psi_e)$ is acceptable, there is a computable bijection $\pi : \nat \to \nat$ with $\psi_e = \Phi_{\pi(e)}$. We admit this isomorphism theorem, proved in Rogers’ paper of 1958 cited below; its proof is a computable back-and-forth argument using the padding lemma. It shows that every result of this course that is stated in terms of indices holds for every acceptable numbering. Not every numbering is acceptable: Friedberg constructed a numbering satisfying the first condition in which each partial computable function appears exactly once. Such a numbering cannot be acceptable: by the isomorphism theorem, the indices of a function in an acceptable numbering are in bijection with its indices in $(\Phi_e)$, which are infinitely many by Corollary 2.6.

2.5 Exercises

Exercise 2.9 ★.

Show that there is a total computable function $g$ such that $\Phi_{g(e)}(x) \simeq 2 \cdot \Phi_e(x)$ for all $e$ and $x$, and that $g$ can be chosen injective.

Solution

Apply Corollary 2.3 to $f(e, x) \simeq 2 \cdot \Phi_e(x)$, to get $s$ with $\Phi_{s(e)} = 2 \cdot \Phi_e$. To make it injective, let $g(0) = s(0)$ and $g(e+1) = p(s(e+1), g(e) + 1)$, where $p$ is the padding function. Then $g(e+1) \geq g(e) + 1$, so $g$ is strictly increasing, hence injective, and $\Phi_{g(e)} = \Phi_{s(e)}$.

Exercise 2.10 ★★.

Show that there is no total computable function $f$ such that, for every $e$, $\Phi_{f(e)}$ is total, and $\Phi_{f(e)} = \Phi_e$ whenever $\Phi_e$ is total.

Solution

Suppose $f$ exists. Then $\Phi_{f(0)}, \Phi_{f(1)}, \dots$ is a sequence of total functions, uniformly computable since $(e, x) \mapsto \Phi_{f(e)}(x)$ is partial computable and total. It contains every total computable function $\Phi_e$, as $\Phi_{f(e)}$. This contradicts Theorem 6.4 of “Diagonalization and computation”.

2.6 Notes and references

The universal function is Turing’s universal machine (1936), and the SMN theorem is due to Kleene (1938). Acceptable numberings and the isomorphism theorem are due to Rogers (1958); Friedberg’s numbering without repetitions appeared the same year.

• A. M. Turing, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society (2) 42 (1936), 230–265.
• S. C. Kleene, On notation for ordinal numbers, Journal of Symbolic Logic 3 (1938), 150–155.
• H. Rogers, Gödel numberings of partial recursive functions, Journal of Symbolic Logic 23 (1958), 331–341.
• R. M. Friedberg, Three theorems on recursive enumeration, Journal of Symbolic Logic 23 (1958), 309–316.