Contents / Mathematical Logic / Computability Theory

Chapter 6

Computability Theory

Turing machines, recursive functions, decidable and r.e. sets, the halting problem, reductions, Rice's theorem, the arithmetical hierarchy and Turing degrees.

Introduction

Computability theory asks which functions and which questions can be settled by a purely mechanical procedure. The answer turns out to be sharp: there is a single robust class of computable functions, reached independently by half a dozen unrelated formalisms, and there are concrete, entirely natural questions — does this program stop? — that provably lie outside it.

The chapter builds the machinery in the order the proofs need it. Turing machines and the recursive functions give two definitions of algorithm; the universal machine and the $s$ - $m$ - $n$ theorem give the two tools that let programs manipulate programs; diagonalisation then produces the first undecidable set, reductions propagate undecidability outwards from it, Rice's theorem shows how far it spreads, and the arithmetical hierarchy and the Turing jump measure what is left.

One warning about scope. Computability measures whether a function can be computed at all, never how cheaply. Complexity classes such as $P$ and $NP$ live one level down and are not treated here. The dual question — how much information a single finite string contains, measured by the length of the shortest program that prints it — is Kolmogorov complexity, and it is developed in the information-theory chapter Algorithmic Information; we use its vocabulary only in passing.

6.1Turing Machines, Configurations and Computation

A definition of "mechanical procedure" has to be poor in features, or the definition smuggles in the very power it is supposed to explain. Turing's device is deliberately impoverished: a finite control, a tape that is unbounded but written one cell at a time, and a head that moves one step per instruction. Everything else — arithmetic, recursion, self-reference — is reconstructed from those pieces.

Definition 6.1 (Turing machine). A Turing machine is a $7$ -tuple

M = (Q, Σ, Γ, δ, q_{0}, q_{acc}, q_{rej}),

where $Q$ is a finite set of states; $Σ$ is the finite input alphabet; $Γ \supseteq Σ$ is the finite tape alphabet, containing a blank symbol $⊔ \in / Σ$ ; $q_{0} \in Q$ is the start state; $q_{acc} \neq = q_{rej}$ are the two halting states; and

δ : (Q ∖ {q_{acc}, q_{rej}}) \times Γ ⟶ Q \times Γ \times {L, R}

is the transition function. The tape is infinite to the right, initially holds the input followed by blanks, and the head starts on the leftmost cell.

The transition function is total on non-halting states, so a computation never gets stuck for want of an instruction: it either reaches $q_{acc}$ or $q_{rej}$ , or it runs forever. That is the only way a Turing machine can fail, and it is exactly the failure the rest of the chapter is about.

Definition 6.2 (Configuration). A configuration of $M$ is a string $u q v$ with $u, v \in Γ^{*}$ and $q \in Q$ : the tape holds $uv$ followed by blanks, the machine is in state $q$ , and the head scans the first symbol of $v$ (a blank if $v$ is empty).

Configuration $C_{1}$ yields $C_{2}$ , written $C_{1} ⊢ C_{2}$ , when one application of $δ$ turns the first into the second. Writing $a, b, c \in Γ$ : if $δ (q, b) = (r, c, R)$ then $u a q b v ⊢ u a c r v$ , and if $δ (q, b) = (r, c, L)$ then $u a q b v ⊢ u r a c v$ . The start configuration on input $w$ is $q_{0} w$ .

Figure 6.3. One step of a machine in configuration

01 q_{3} 10

. The head scans the highlighted cell;

δ (q_{3}, 1) = (q_{5}, 0, R)

rewrites it and shifts the head one cell right, producing

010 q_{5} 0

A computation is now just a chain of configurations. This is the level at which almost every later proof operates: nobody writes transition tables after this section, but the fact that a computation is a finite string of finite configurations is what makes computations checkable, encodable and countable.

Definition 6.4 (Computation, acceptance, computed function). The computation of $M$ on $w$ is the (finite or infinite) sequence $C_{0} ⊢ C_{1} ⊢ C_{2} ⊢ \dots$ with $C_{0} = q_{0} w$ . It halts if some $C_{t}$ contains $q_{acc}$ or $q_{rej}$ , and then $t$ is the running time.

$M$ accepts $w$ if it halts in $q_{acc}$ ; $L (M)$ is the set of accepted strings. $M$ decides $L (M)$ if it halts on every input. The partial function computed by $M$ , written $φ_{M}$ , sends $w$ to the tape contents at halting if $M$ halts on $w$ , and is undefined otherwise; we write $φ_{M} (w) ↓$ for "defined" (the machine halts) and $φ_{M} (w) ↑$ for "undefined".

Definition 6.5 (Computable and partial computable). A partial function $f$ on $N$ is partial computable (partial recursive) if $f = φ_{M}$ for some Turing machine $M$ . It is computable (total recursive) if in addition it is total, i.e. the machine halts on every input.

Pitfall. Halting and accepting are different events, and recognising and deciding are different achievements. A machine that accepts exactly the members of $A$ but runs forever on some non-members recognises $A$ without deciding it. Almost every undecidability result in this chapter is the statement that some set is recognised but not decided.

Example 6.6 (A machine, traced by configurations). Specify a Turing machine computing the successor on unary notation — the number $n$ is the block $1^{n}$ — and trace its computation on $n = 2$ as a chain of configurations.

Solution. Take $Γ = {1, ⊔}$ , states ${q_{0}, q_{acc}, q_{rej}}$ , and

δ (q_{0}, 1) = (q_{0}, 1, R), δ (q_{0}, ⊔) = (q_{acc}, 1, R) .

The machine walks right over the block and converts the first blank into a $1$ . On input $11$ :

q_{0} 11 ⊢ 1 q_{0} 1 ⊢ 11 q_{0} ⊢ 111 q_{acc} .

Three steps, and the tape reads $111 = 3 = 2 + 1$ . On input $1^{n}$ the machine takes exactly $n + 1$ steps, so it halts on every input and the successor is total computable. Note that the table has two lines no matter how large $n$ is: a finite program, uniform in the input, is the whole point of the model. □□

Nothing in these traces depends on having one tape, or on the tape being one-dimensional, or on the machine being deterministic. That robustness is what entitles us to stop drawing tables.

Theorem 6.7 (Robustness of the model). Each of the following computes exactly the partial computable functions: single-tape machines; $k$ -tape machines for any fixed $k$ ; machines with a two-way infinite tape; machines with a two-dimensional tape; nondeterministic machines; and register machines. In particular a function is computable by some multi-tape machine if and only if it is computable by some single-tape machine.

Proof. We give the simulation for $k$ tapes in full and sketch the rest. Given a $k$ -tape machine $N$ , build a single-tape $M$ over the enlarged alphabet $Γ \cup \dot{Γ} \cup {#}$ , where $\overset{a}{˙}$ is a dotted copy of $a$ marking a head position. $M$ keeps the $k$ tapes on one tape as $# u_{1} # u_{2} # \dots # u_{k} #$ , with exactly one dotted symbol per block. To simulate one step of $N$ , $M$ sweeps the whole tape once to read the $k$ scanned symbols — it can remember them in its finite control, since $k$ is a fixed constant and the alphabet is finite — consults $N$ 's table, and sweeps back writing the new symbols and moving the dots one cell each; when a dot would run off the right end of a block, $M$ first shifts everything to the right of that block one cell rightwards to make room. Each simulated step is therefore faithful, so by induction on $t$ the tape of $M$ after simulating $t$ steps encodes the configuration of $N$ after $t$ steps. Hence $M$ halts exactly when $N$ does and with the same output, so $φ_{M} = φ_{N}$ ; the converse inclusion is trivial, a $1$ -tape machine being a $k$ -tape machine that ignores $k - 1$ tapes.

For the remaining models the same "encode the state of the other device on one tape and simulate a step at a time" argument applies: a two-way infinite tape is folded into two interleaved tracks of a one-way tape, a two-dimensional tape is stored as a list of written cells with their coordinates, a register machine's registers are stored as separated blocks, and a nondeterministic machine is simulated by breadth-first search over its computation tree, one depth at a time — depth-first would be unfaithful, since it can fall into an infinite branch while an accepting branch exists elsewhere. What these arguments do not claim is that the simulations are cheap: the $k$ -tape simulation above costs $O (t^{2})$ steps for $t$ simulated steps, and the nondeterministic one costs exponentially. Cost is a complexity question and is irrelevant to the class of computable functions.∎

Encoding is the other thing this section owes the rest of the chapter. A machine is a finite object, so it can be written down as a string, and strings can be numbered.

Definition 6.8 (Encoding and the standard listing). Fix an effective encoding $M \mapsto ⟨ M ⟩ \in N$ of Turing machines as numbers, and an effective pairing bijection $⟨ \cdot, \cdot ⟩ : N^{2} \to N$ , for example the Cantor pairing

⟨ x, y ⟩ = \frac{1}{2} (x + y) (x + y + 1) + y .

Every number is taken to be the code of some machine (decode garbage as a fixed trivial machine). Write $M_{e}$ for the machine coded by $e$ and

φ_{e} := φ_{M_{e}}

for the partial computable function it computes. The sequence $φ_{0}, φ_{1}, φ_{2}, \dots$ is the standard listing of the partial computable functions; $e$ is an index for $φ_{e}$ . Every partial computable function has infinitely many indices, since padding a machine with unreachable states changes the code but not the function.

That listing immediately settles how much of mathematics is computable: almost none of it.

Theorem 6.9 (Most functions are not computable). There are only countably many partial computable functions, but uncountably many functions $N \to {0, 1}$ . Hence uncountably many functions $N \to N$ are not computable, and likewise only countably many subsets of $N$ are decidable.

Proof. Each Turing machine is a finite tuple over finite sets, so it has a finite description over a fixed finite alphabet; there are countably many finite strings over a finite alphabet, and $e \mapsto φ_{e}$ maps $N$ onto the partial computable functions, which are therefore countably many. The functions $N \to {0, 1}$ are in bijection with $P (N)$ , which by Cantor's theorem has cardinality $2^{ℵ_{0}} > ℵ_{0}$ . A countable set cannot contain an uncountable one, so the non-computable functions are uncountable — indeed all but countably many functions are uncomputable.∎

Intuition. Programs are finite texts, and there are only countably many finite texts. Functions on $N$ are infinite objects with no such constraint, and there are continuum-many. The mismatch is so violent that a "random" function is uncomputable with probability one. What the rest of the chapter adds is that undecidability is not confined to those exotic objects: the halting set is as concrete and as natural as a set can be.

Pitfall. The counting argument proves that uncomputable functions exist; it exhibits none, and it cannot, because it never mentions a specific function. Producing a named undecidable set takes diagonalisation, which is the work of the section The Halting Problem.

Exercises for §6.1 →

6.2Recursive Functions and the Church-Turing Thesis

The second definition of algorithm never mentions a machine. It builds functions algebraically from a handful of obviously-computable seeds using rules that obviously preserve computability, and the surprise is that this reaches exactly as far as the tape does.

Definition 6.10 (Primitive recursive functions). The primitive recursive functions form the smallest class of total functions $N^{k} \to N$ containing the base functions

the zero function $Z (x) = 0$ ,
the successor $S (x) = x + 1$ ,
the projections $P_{i}^{n} (x_{1}, \dots, x_{n}) = x_{i}$ for $1 \leq i \leq n$ ,

and closed under

composition: $h (x) = f (g_{1} (x), \dots, g_{k} (x))$ ;
primitive recursion: from $g$ of arity $n$ and $h$ of arity $n + 2$ , the function $f$ of arity $n + 1$ given by

f (x, 0) = g (x), f (x, y + 1) = h (x, y, f (x, y)) .

The recursion parameter $y$ counts down to a base case reached after exactly $y$ unfoldings, so the schema is a bounded loop: the trip count is known before the loop starts. That is the structural reason for the following, and it is also the class's limitation.

Theorem 6.11 (Primitive recursive implies total). Every primitive recursive function is total.

Proof. Induct on the derivation of the function. The three base functions are total. If $f, g_{1}, \dots, g_{k}$ are total then so is the composition $f (g_{1} (x), \dots, g_{k} (x))$ , since every inner value is defined and $f$ is defined everywhere. Suppose $g$ and $h$ are total and $f$ arises from them by primitive recursion. Fix $x$ and induct on $y$ : $f (x, 0) = g (x)$ is defined, and if $f (x, y)$ is defined then $f (x, y + 1) = h (x, y, f (x, y))$ is defined because $h$ is total. So $f$ is defined at every $(x, y)$ .∎

Example 6.12 (Building the arithmetic you need). Show that addition, multiplication, the predecessor, truncated subtraction and the sign function are primitive recursive, and record the derived tools they give.

Solution. Addition fits the schema with $g = P_{1}^{1}$ and $h (x, y, z) = S (P_{3}^{3} (x, y, z))$ :

add (x, 0) = x, add (x, y + 1) = S (add (x, y)) .

Unfolding checks it: $add (2, 3) = S (add (2, 2)) = S (S (add (2, 1))) = S (S (S (add (2, 0)))) = S (S (S (2))) = 5$ , bottoming out after exactly $3$ unfoldings.

Multiplication uses $add$ as its step, $mult (x, 0) = 0$ and $mult (x, y + 1) = add (x, mult (x, y))$ ; exponentiation uses $mult$ the same way. The predecessor is a recursion that discards its recursive value, $pred (0) = 0$ and $pred (y + 1) = y$ , and truncated subtraction iterates it: $x \dot{-} 0 = x$ and $x \dot{-} (y + 1) = pred (x \dot{-} y)$ . The sign function is $sg (x) = 1 \dot{-} (1 \dot{-} x)$ , which is $0$ at $0$ and $1$ elsewhere.

With $sg$ and $\dot{-}$ in hand, predicates become primitive recursive too, identifying a predicate with its characteristic function: the characteristic function of $x \leq y$ is $1 \dot{-} (x \dot{-} y)$ , and $\land, \lor, \neg$ are computed by $mult$ , by $sg \circ add$ and by $1 \dot{-} x$ . Bounded sums and products $\sum_{i < y} f (x, i)$ and $\prod_{i < y} f (x, i)$ are primitive recursions, and so is bounded search

(μ i < y) [R (x, i)] = the least i < y with R (x, i), and y if there is none,

since it can be written as a bounded sum of products of $sg$ values. Everything up to and including "is $x$ prime?", "what is the $n$ -th prime?" and the decoding of sequence codes is therefore primitive recursive. □□

Totality is a ceiling as well as a guarantee. A class of total functions cannot contain a function universal for itself, and it cannot contain the fastest-growing total functions.

Theorem 6.13 (Ackermann's function). Define $A : N^{2} \to N$ by

A (0, n) = n + 1, A (m + 1, 0) = A (m, 1), A (m + 1, n + 1) = A (m, A (m + 1, n)) .

Then $A$ is total and computable, but $A$ is not primitive recursive.

Proof. Sketch, complete except for the majorisation lemma named below. Totality follows by induction on $(m, n)$ ordered lexicographically: every right-hand side calls $A$ at a lexicographically smaller pair, and the lexicographic order on $N^{2}$ is a well-order, so the recursion terminates. It is computable because the recursion is a finite, effective rewriting procedure that the Church-Turing thesis (or an explicit stack machine) turns into a program.

Non-primitive-recursiveness rests on a majorisation lemma, proved by induction on the build of $f$ : for every primitive recursive $f$ of arity $k$ there is an $m$ with

f (x_{1}, \dots, x_{k}) < A (m, i max x_{i}) for all x .

The inductive step needs the monotonicity facts $A (m, n) < A (m, n + 1)$ and $A (m, n) \leq A (m + 1, n)$ , each itself an induction, and composition and primitive recursion each raise the required $m$ by a bounded amount. Granting the lemma, suppose $A$ were primitive recursive. Then so would be the diagonal $d (x) = A (x, x)$ , so $d (x) < A (m, x)$ for some fixed $m$ and all $x$ ; taking $x = m$ gives $A (m, m) < A (m, m)$ , a contradiction. The step left unproved here is the majorisation lemma, a long but routine double induction.∎

Intuition. Ackermann's function diagonalises out of the primitive recursive class in the same way the halting argument will diagonalise out of the computable one, and the reason is the same: a class closed under a uniform construction cannot contain the function that runs down its own list doing something different. Concretely, $A (1, n)$ is essentially $n + 2$ , $A (2, n)$ is essentially $2 n$ , $A (3, n)$ is essentially $2^{n}$ , and $A (4, n)$ a tower of exponentials — each row outgrows every function definable with one fewer level of loop nesting.

To reach the partial functions — and every function a real programming language can define, since a real program can loop — one more rule is needed, and exactly one.

Definition 6.14 (Partial recursive functions). The $μ$ -operator (unbounded search) applied to a partial function $g$ of arity $n + 1$ yields

μ y [g (x, y) = 0] = the least y such that g (x, y) = 0 and g (x, i) ↓ for all i \leq y,

undefined if no such $y$ exists. The partial recursive functions are the smallest class containing the base functions and closed under composition, primitive recursion and $μ$ . A partial recursive function that happens to be total is called total recursive.

Pitfall. $μ$ is the only source of divergence, and it diverges in two distinct ways: either no witness $y$ exists at all, or some earlier value $g (x, i)$ is itself undefined and the search hangs before reaching a witness. The clause " $g (x, i) ↓$ for all $i \leq y$ " is not pedantry — without it the operator would be uncomputable, since it would demand the least witness while forbidding the machine to test the values below it.

Theorem 6.15 (Kleene normal form, and equivalence with Turing computability). There is a primitive recursive predicate $T (e, x, s)$ — " $s$ codes a halting computation of $M_{e}$ on input $x$ " — and a primitive recursive function $U$ ("read the output off a computation") such that for every partial computable $f$ there is an index $e$ with

f (x) ≃ U (μ s [T (e, x, s)])

for all $x$ , where $≃$ means the two sides are defined for exactly the same $x$ and are equal there. Consequently a partial function is partial recursive if and only if it is Turing computable, and a single application of $μ$ to a primitive recursive predicate always suffices.

Proof. Sketch, resting on the arithmetisation of syntax named at the end. Both directions are simulations. Recursive $\Rightarrow$ Turing computable: each base function has a two-line machine, composition is sequencing, primitive recursion is a counted loop, and $μ$ is an unbounded loop — every rule has a direct machine implementation, so induction on the build gives a machine for every partial recursive function.

Turing computable $\Rightarrow$ recursive: encode a configuration $u q v$ as a number by coding the finite strings $u$ and $v$ symbol by symbol, and code a length- $t$ computation history as a single number $s$ by the prime-power sequence coding $s = \prod_{i < t} p_{i}^{c_{i}}$ . Then "is $c_{i + 1}$ the successor configuration of $c_{i}$ under the table coded by $e$ ? " is a bounded arithmetic question about the exponents of $s$ , hence primitive recursive by the tools built above; conjoining it over $i < lh (s)$ with bounded quantifiers, and adding " $c_{0}$ is the start configuration on $x$ " and "the last configuration is halting", gives the primitive recursive predicate $T$ . Searching for a halting history is the single $μ$ , and $U$ extracts the output from the last configuration.

What the sketch compresses is the arithmetisation itself: the verification that sequence coding, decoding and length are primitive recursive. That is the content of Gödel's $β$ -function lemma, proved in the chapter Incompleteness and Independence, and everything here rests on it.∎

Remark (The Church-Turing thesis). Thesis. A function is effectively calculable — computable by some finite, deterministic, mechanical procedure in the informal sense — precisely when it is partial recursive, equivalently Turing computable.

This is a thesis, not a theorem, and it cannot be one: "effectively calculable" is an informal notion, so there is nothing to prove it against. What supports it is evidence. Turing machines, the $λ$ -calculus, Gödel-Herbrand general recursion, Post systems, register machines, Markov algorithms and every programming language ever implemented define the same class, despite having been designed with different intentions. Turing's own argument is the most direct: he analysed what a human computer with paper, finitely many distinguishable states of mind and a bounded field of view can do in one step, and showed that each such step is a Turing-machine step.

The thesis is refutable in principle. Exhibiting a physically realisable procedure that computes a function provably outside the class would kill it. None has been produced; quantum computers, analogue machines and randomised algorithms all compute exactly the same class of functions, differing only in cost.

Pitfall. Do not cite the Church-Turing thesis inside a proof as though it were a theorem, and do not confuse it with the false claim that "everything is computable". The thesis says the two classes coincide; Theorem Most functions are not computable showed the class is countable, so it misses almost every function.

Intuition. In practice the thesis is a licence to stop writing transition tables. Once you accept it, "there is an algorithm that does $X$ " is enough to conclude "there is a Turing machine computing $X$ ", and every later construction in this chapter — build a machine that simulates another on a modified input, search for a halting computation, dovetail infinitely many simulations at once — is described in that informal register and is none the worse for it.

Exercises for §6.2 →

6.3Decidable and Recursively Enumerable Sets

Undecidability is a property of sets, so the vocabulary has to be fixed before anything can be proved undecidable. Two notions matter, and the gap between them is where the whole subject lives.

Definition 6.16 (Decidable and recursively enumerable). A set $A \subseteq N$ is decidable (recursive, computable) if its characteristic function

χ_{A} (x) = {10 x \in A, x \in / A

is computable — some machine halts on every input and answers correctly.

$A$ is recursively enumerable (r.e., computably enumerable, semi-decidable) if $A$ is the domain of a partial computable function: for some $e$ ,

A = W_{e} := {x : φ_{e} (x) ↓} .

Equivalently, some machine halts exactly on the members of $A$ and runs forever on the rest.

Notation. $W_{e}$ denotes the $e$ -th r.e. set, the domain of $φ_{e}$ ; the sequence $W_{0}, W_{1}, W_{2}, \dots$ enumerates all r.e. sets, just as $φ_{0}, φ_{1}, \dots$ enumerates all partial computable functions. We write $\overline{A} = N ∖ A$ for the complement.

Intuition. A decider is a machine with a deadline: it must answer, yes or no, in finite time. A semi-decider has only half a deadline — it must eventually say yes when the answer is yes, and is free to stay silent forever when the answer is no. "Silent forever" is not an answer you can ever observe, which is precisely why semi-decidability is strictly weaker.

Two constructions make semi-decidability workable in practice, and both recur constantly below. The first is the stage, or step-counting, view: $x \in W_{e}$ if and only if $φ_{e} (x)$ halts within $s$ steps for some $s$ , and "does $φ_{e} (x)$ halt within $s$ steps?" is decidable — simulate for $s$ steps and look. The second is dovetailing: to run infinitely many computations at once, run computation $0$ for one step, then computations $0$ and $1$ for one more step each, then $0, 1, 2$ , and so on. Every individual computation receives unboundedly many steps, so any one that halts is eventually seen to halt.

Theorem 6.17 (Complementation characterises decidability). A set $A \subseteq N$ is decidable if and only if both $A$ and $\overline{A}$ are recursively enumerable.

Proof. ( $\Rightarrow$ ) Suppose $A$ is decidable, with total machine $D$ computing $χ_{A}$ . A machine that runs $D$ and then halts if the answer is $1$ , and enters a deliberate infinite loop if the answer is $0$ , has domain exactly $A$ ; so $A$ is r.e. Swapping the two branches gives a machine with domain $\overline{A}$ , so $\overline{A}$ is r.e.

( $\Leftarrow$ ) Suppose $A = W_{i}$ and $\overline{A} = W_{j}$ . Build a machine $D$ which, on input $x$ , runs the two computations $φ_{i} (x)$ and $φ_{j} (x)$ in parallel — formally, for $s = 1, 2, 3, \dots$ it simulates each for $s$ steps and tests the decidable predicates " $φ_{i} (x)$ halts within $s$ steps" and " $φ_{j} (x)$ halts within $s$ steps". It stops at the first $s$ at which one of them holds, outputting $1$ if it was the $i$ -computation and $0$ if it was the $j$ -computation.

$D$ halts on every input: $x$ lies in exactly one of $A$ and $\overline{A}$ , so exactly one of $φ_{i} (x)$ , $φ_{j} (x)$ converges, and it converges after some finite number of steps $s_{0}$ ; the loop therefore terminates by stage $s_{0}$ . Because exactly one of the two ever converges, no input can trigger both tests, and the output is unambiguous. And $D$ is correct: it outputs $1$ only when $φ_{i} (x) ↓$ , that is $x \in W_{i} = A$ , and $0$ only when $φ_{j} (x) ↓$ , that is $x \in \overline{A}$ . So $χ_{A}$ is computable and $A$ is decidable.∎

The theorem is the workhorse of the chapter in its contrapositive form: if $A$ is r.e. and not decidable, then $\overline{A}$ is not even r.e. A single undecidability proof therefore yields two sets' worth of information, and it is how we will know, in the next section, that " $M$ does not halt on $w$ " is not merely undecidable but not semi-decidable either.

Theorem 6.18 (Enumeration characterises r.e.). A non-empty set $A \subseteq N$ is r.e. if and only if $A$ is the range of a total computable function. Moreover an infinite set $A$ is decidable if and only if it is the range of a strictly increasing total computable function.

Proof. If $A = ran f$ with $f$ total computable, then the machine that on input $x$ computes $f (0), f (1), f (2), \dots$ and halts at the first $n$ with $f (n) = x$ has domain exactly $A$ , so $A$ is r.e.

Conversely let $A = W_{e}$ be non-empty and fix $a \in A$ . Using the decidable stage predicate and the pairing bijection, define

f (⟨ x, s ⟩) = {x a if φ_{e} (x) halts within s steps, otherwise.

This is total and computable, since the test is decidable and every number is a pair. Its range is contained in $A$ , because it outputs only $a$ and values on which $φ_{e}$ halts; and it contains $A$ , because any $x \in A$ halts at some stage $s$ , whence $x = f (⟨ x, s ⟩)$ .

For the last claim let $A$ be infinite. If $A = ran f$ with $f$ strictly increasing, then to test $x$ compute $f (0) < f (1) < \dots$ until the values exceed $x$ , which happens by index $x + 1$ since $f (n) \geq f (0) + n$ , and check whether $x$ appeared; this always halts, so $A$ is decidable. Conversely if $A$ is infinite and decidable, run the decider on $0, 1, 2, \dots$ and let $f (n)$ be the $n$ -th member found. The search always succeeds because $A$ is infinite, so $f$ is total; it is computable; and it is strictly increasing by construction.∎

Pitfall. "Recursively enumerable" means listable in some order, not in increasing order. The last clause above is exactly that difference: an increasing enumeration lets you stop searching and conclude $x \in / A$ , and that extra power is precisely decidability. Many mistaken arguments that the halting set is decidable amount to forgetting this.

Programs must now become data that other programs can read and write. Two theorems make that legal, and every construction from here to the end of the chapter uses one or both.

Theorem 6.19 (Universal machine, or the enumeration theorem). There is a partial computable function of two arguments, computed by a single machine $U$ , with

U (e, x) ≃ φ_{e} (x) for all e, x .

Consequently the set $K_{0} = {⟨ e, x ⟩ : φ_{e} (x) ↓}$ is r.e.

Proof. Sketch, honest about the one routine but tedious step. On input $(e, x)$ , $U$ decodes $e$ into a transition table, writes the start configuration $q_{0} x$ on a work tape, and then repeatedly performs the operation "given a configuration and the table, produce its successor configuration". That operation is decidable: it is a bounded search through the finitely many table entries for the one matching the current state and scanned symbol, followed by a local rewrite of the configuration string. $U$ halts exactly when the simulated machine reaches a halting state, and then copies the output; so $U (e, x) ↓$ if and only if $φ_{e} (x) ↓$ , with the same value. Since $U$ halts exactly on the pairs $⟨ e, x ⟩$ with $φ_{e} (x) ↓$ , that set is the domain of a partial computable function and hence r.e.

The step compressed is the bookkeeping: a single tape must hold the table, the simulated tape and a marker for the simulated head, and shifting cells to make room requires care. Theorem Robustness of the model lets us carry out the construction on a three-tape machine, where it is immediate, and then convert.∎

Theorem 6.20 (The $s$ - $m$ - $n$ theorem). For all $m, n \geq 1$ there is a total computable, injective function $s_{n}^{m}$ of $m + 1$ arguments such that

φ_{s_{n}^{m} (e, y_{1}, \dots, y_{m})} (x_{1}, \dots, x_{n}) ≃ φ_{e} (y_{1}, \dots, y_{m}, x_{1}, \dots, x_{n})

for all $e$ and all arguments, where on each side $φ$ denotes the standard listing of partial computable functions of the appropriate arity. In words: fixing some of a program's inputs can be carried out on the program text, computably and uniformly.

Proof. Sketch. Given $e$ and $y$ , the function $s_{n}^{m}$ outputs the code of the machine that, on input $x$ , first writes the fixed constants $y$ to the left of its input — a preamble of finitely many states depending only on the numerals $y$ — and then runs $M_{e}$ . Building this code is textual splicing: read off the table of $e$ , renumber its states to make room, prepend the preamble, and re-encode. Every step is a primitive recursive operation on the code, so $s_{n}^{m}$ is total computable, and padding the preamble with unreachable states makes it injective. The displayed equivalence holds because the constructed machine's computation on $x$ is, after the preamble, literally the computation of $M_{e}$ on $(y, x)$ . What is not spelled out here is the encoding-level detail of the renumbering, which depends on the coding fixed in Definition Encoding and the standard listing.∎

Intuition. The $s$ - $m$ - $n$ theorem is currying, and you have used it whenever you wrote a closure or a partial application. Its content is not that partial application exists but that it is effective on the code: there is an algorithm taking a program and some inputs to a new program. That is what licenses a proof to say "let $f$ be the total computable function with $φ_{f (x)} = \dots$ ", which is how every reduction in this chapter is built.

Example 6.21 (Building a program that ignores its input). Given $e$ , construct — computably in $e$ — an index $g (e)$ with $φ_{g (e)} (y) ≃ φ_{e} (e)$ for every $y$ : a program that discards its own input and instead runs $M_{e}$ on $e$ .

Solution. Define the partial computable function of two arguments

θ (x, y) ≃ φ_{x} (x),

which is partial computable because it is $U (x, x)$ for the universal machine $U$ , with $y$ discarded. Fix an index $d$ for $θ$ as a function of two arguments. By $s$ - $m$ - $n$ with $m = n = 1$ put

g (e) := s_{1}^{1} (d, e) .

Then $g$ is total computable, being the total computable $s_{1}^{1}$ with its first argument fixed, and for every $y$

φ_{g (e)} (y) ≃ θ (e, y) ≃ φ_{e} (e) .

So $φ_{g (e)}$ is the everywhere-undefined function when $φ_{e} (e) ↑$ , and a constant total function when $φ_{e} (e) ↓$ . This three-line pattern — define the partial function you want, take an index for it, apply $s$ - $m$ - $n$ — is the engine of every reduction in the following sections and of the proof of Rice's theorem. □□

Proposition 6.22 (Closure properties). The decidable sets are closed under complement, union and intersection. The r.e. sets are closed under union and intersection, but not under complement.

Proof. For decidable sets, run the deciders and combine their answers with $\neg, \lor, \land$ ; all deciders are total, so the combination halts on every input.

For r.e. sets $A = W_{i}$ and $B = W_{j}$ : for the intersection, run $φ_{i} (x)$ and then $φ_{j} (x)$ in sequence and halt only if both halt, which gives domain $A \cap B$ . For the union, run the two in parallel by stages exactly as in the proof of Theorem Complementation characterises decidability and halt as soon as either halts, giving domain $A \cup B$ . Failure of closure under complement follows from Theorem Complementation characterises decidability together with the existence, proved in the next section, of an r.e. set that is not decidable: were the r.e. sets closed under complement, every r.e. set would have r.e. complement and hence be decidable.∎

Exercises for §6.3 →

6.4The Halting Problem and Diagonalisation

Everything so far has been machinery. This section spends it, producing a concrete, completely natural set that no algorithm decides.

Definition 6.23 (The halting problem). The halting problem is the set

K_{0} = {⟨ e, x ⟩ : φ_{e} (x) ↓},

"does program $e$ halt on input $x$ ? ". Its diagonal version is

K = {e : φ_{e} (e) ↓},

the set of programs that halt when run on their own code. $K$ is also written $\emptyset^{'}$ and called the halting set.

Both sets are r.e.: by Theorem Universal machine, or the enumeration theorem, $K_{0}$ is the domain of $U$ , and $K$ is the domain of $x \mapsto U (x, x)$ . So halting is semi-decidable — run the machine and say yes if it stops. What cannot be done is to ever say no.

Theorem 6.24 (Undecidability of the halting problem). $K$ is not decidable, and neither is $K_{0}$ . Hence there is no algorithm which, given a program and an input, always halts and correctly reports whether that program halts on that input.

Proof. Suppose $K$ were decidable. Then the partial function

g (x) ≃ {0 undefined if x \in / K, if x \in K

would be partial computable: run the assumed total decider for $K$ on $x$ , output $0$ if it says "no", and enter a deliberate infinite loop if it says "yes". Being partial computable, $g = φ_{i}$ for some index $i$ . Now ask whether $i \in K$ :

i \in K ⟺ φ_{i} (i) ↓ ⟺ g (i) ↓ ⟺ i \in / K,

where the first equivalence is the definition of $K$ , the second is $g = φ_{i}$ , and the third is the definition of $g$ . This is a contradiction, so no decider for $K$ exists.

For $K_{0}$ : a decider for $K_{0}$ would decide $K$ , since $x \in K ⟺ ⟨ x, x ⟩ \in K_{0}$ and $x \mapsto ⟨ x, x ⟩$ is computable. So $K_{0}$ is undecidable too.∎

Intuition. The argument is Cantor's diagonal argument wearing different clothes. Lay out the infinite table whose $(i, x)$ entry records whether $φ_{i} (x)$ halts. A decider for $K$ would let us compute the diagonal of that table, and $g$ is built to disagree with the diagonal at every point: it halts exactly where the diagonal says "does not halt". But $g$ is itself one of the rows, say row $i$ , and a row cannot differ from the diagonal at its own position. Cantor built a real not in the list; Turing built a program not in the list of programs, which is impossible, so the assumed decider is what fails.

Corollary 6.25 (The complement of $K$ is not even r.e.). $\overline{K} = {e : φ_{e} (e) ↑}$ is not recursively enumerable. Likewise $\overline{K_{0}}$ , the set of pairs $⟨ e, x ⟩$ such that $M_{e}$ runs forever on $x$ , is not r.e.

Proof. $K$ is r.e. and, by Theorem Undecidability of the halting problem, not decidable. If $\overline{K}$ were r.e. as well, Theorem Complementation characterises decidability would make $K$ decidable. The same argument applies to $K_{0}$ .∎

So the two halves of the halting question are not symmetric. "This program halts" is confirmable in finite time whenever it is true; "this program never halts" is not confirmable even in principle by any uniform procedure, which is why non-termination proofs are always specific to the program at hand.

Pitfall. Undecidability of halting is not the claim that no program's behaviour can ever be determined. For any particular program you may well have a proof that it halts — the successor machine above halts in $n + 1$ steps, and that is a theorem. The undecidable object is the uniform question, one algorithm answering for all pairs. Likewise, undecidability says nothing about approximations: compilers, termination checkers and static analysers are sound but incomplete, answering "halts", "loops", or "don't know", and that third option is exactly what makes them possible.

Example 6.26 (Halting on the empty input). Show that $HALT_{ε} = {e : φ_{e} (0) ↓}$ — "does this program halt on the fixed input $0$ ? " — is undecidable, even though the input is no longer a parameter.

Solution. Use Example Building a program that ignores its input: the total computable $g$ there satisfies $φ_{g (e)} (y) ≃ φ_{e} (e)$ for every $y$ . In particular

φ_{g (e)} (0) ↓ ⟺ φ_{e} (e) ↓ ⟺ e \in K .

Suppose $HALT_{ε}$ had a total decider $E$ . Then $x \mapsto E (g (x))$ is total computable and decides $K$ : it answers yes exactly when $φ_{g (x)} (0) ↓$ , that is, exactly when $x \in K$ . This contradicts Theorem Undecidability of the halting problem, so no such $E$ exists.

Note the direction, which is the whole content of the argument: we turned a decider for the target problem into a decider for the known-undecidable one. Building a decider for the halting problem out of a decider for $HALT_{ε}$ would prove nothing about $HALT_{ε}$ at all. □□

Undecidability also has a quantitative shadow: a function that is perfectly well defined and grows faster than every computable function.

Definition 6.27 (The busy beaver function). For $n \geq 1$ let $BB (n)$ be the largest number of $1$ s that any $n$ -state, two-symbol Turing machine can leave on an initially blank tape before halting, the maximum being taken over the finitely many such machines that do halt.

Theorem 6.28 (Busy beaver is not computable). $BB$ is not computable. Indeed $BB$ eventually exceeds every computable function: for every computable $f : N \to N$ there is an $N$ with $BB (n) > f (n)$ for all $n \geq N$ .

Proof. Suppose $BB$ were computable, and let $S (n)$ be the maximum number of steps taken by a halting $n$ -state machine on the blank tape; the same argument applies to either, and $S$ is computable if $BB$ is, since one may run each halting machine to completion once its output length is known to be bounded. Then halting on the blank tape becomes decidable: given an $n$ -state machine, simulate it for $S (n)$ steps, and if it has not halted by then it never will, because $S (n)$ bounds the running time of every halting $n$ -state machine. This contradicts the undecidability of blank-tape halting, which follows from Example Halting on the empty input by translating "input $0$ " into "blank tape" — a fixed change of encoding.

For the growth claim, let $f$ be computable and consider $F (n) = max_{i \leq n} f (i) + n + 1$ , which is computable, total and non-decreasing. There is a fixed machine of some size $c$ computing $F$ , so an $n$ -state machine can be built, for suitable small overhead, that writes $n$ in unary and then runs it; this puts $F (n)$ ones on the tape using $n + c$ states, whence $BB (n + c) \geq F (n) > f (n)$ . Since $BB$ is non-decreasing in $n$ , this forces $BB$ past $f$ from some point on.∎

Example 6.29 (The known busy beaver values). The values of $BB (n)$ for small $n$ are $BB (1) = 1$ , $BB (2) = 4$ , $BB (3) = 6$ , $BB (4) = 13$ , and $BB (5) = 4098$ . Explain why the sequence stops there.

Solution. For each fixed $n$ there are only finitely many $n$ -state two-symbol machines — about $(4 n + 4)^{2 n}$ of them — so $BB (n)$ is a perfectly well-defined natural number, and in principle each value is found by examining a finite list. What is not finite is the work of deciding, for each machine on that list, whether it halts at all: a machine that has not halted after a trillion steps might still halt, and no uniform test can tell. Determining $BB (5)$ required resolving the behaviour of every hold-out machine individually, and $BB (6)$ is known to exceed $10 ↑↑ 15$ , a tower of exponentials, so it will never be pinned down by simulation.

This is Theorem Busy beaver is not computable seen from ground level: the difficulty is not that the values are large, but that no single algorithm produces them, so each new value demands a new mathematical argument. □□

Remark (What undecidability spread to). Many problems far from machine theory are undecidable, each by a reduction from halting: validity in first-order logic (the Entscheidungsproblem, Church and Turing 1936); whether a Diophantine equation has an integer solution (Hilbert's tenth problem, by the MRDP theorem); whether two context-free grammars generate the same language; whether a set of Wang tiles tiles the plane; and the word problem for finitely presented groups. The pattern is always the same: encode the computation history of a machine as an object of the target kind, so that a decision procedure for the target would read off whether the machine halts.

Exercises for §6.4 →

6.5Reductions: Transporting Undecidability

One undecidable set is enough, provided there is a disciplined way to carry its undecidability elsewhere. That way is reduction, and formalising it turns a collection of ad-hoc contradiction arguments into a single lemma applied over and over.

Definition 6.30 (Many-one reducibility). Let $A, B \subseteq N$ . Then $A$ is many-one reducible to $B$ , written $A \leq_{m} B$ , if there is a total computable $f$ with

x \in A ⟺ f (x) \in B for all x \in N .

If in addition $f$ is injective the reduction is one-one, written $A \leq_{1} B$ . Sets with $A \leq_{m} B$ and $B \leq_{m} A$ are many-one equivalent, $A \equiv_{m} B$ .

Intuition. Read $A \leq_{m} B$ as " $A$ is no harder than $B$ ": questions about $A$ can be rephrased, by a fixed algorithm, as questions about $B$ . The function $f$ does no deciding — it is total, so it always returns, and it never learns the answer. It only translates. All the difficulty stays in $B$ .

Theorem 6.31 (Reduction transfers decidability and enumerability). Suppose $A \leq_{m} B$ . Then:

if $B$ is decidable, so is $A$ ;
if $B$ is r.e., so is $A$ ;
contrapositively, if $A$ is undecidable then so is $B$ , and if $A$ is not r.e. then neither is $B$ .

Proof. Let $f$ be total computable with $x \in A ⟺ f (x) \in B$ .

(1) If $D$ is a total decider for $B$ , then $x \mapsto D (f (x))$ is total — both $f$ and $D$ halt on every input — and outputs $1$ exactly when $f (x) \in B$ , that is exactly when $x \in A$ . So it decides $A$ .

(2) If $B = W_{j}$ , consider the machine that on input $x$ computes $f (x)$ and then runs $φ_{j}$ on it. It halts iff $φ_{j} (f (x)) ↓$ iff $f (x) \in B$ iff $x \in A$ , so its domain is $A$ and $A$ is r.e.

(3) is the contrapositive of (1) and (2).∎

Pitfall. The direction is the entire content, and reversing it proves nothing. To show a target $B$ is undecidable you must reduce a known-undecidable $A$ to $B$ : $A \leq_{m} B$ , translating questions about halting into questions about $B$ . Writing $B \leq_{m} A$ instead shows only that $B$ is no harder than something hard, which is vacuous. A quick check: the reduction must start from an arbitrary instance of the hard problem and produce an instance of the target.

Method 6.32 (Proving a set $B$ undecidable by reduction).

Choose a known-undecidable source, almost always $K$ .
Describe, in plain algorithmic language, a program $P_{x}$ built from the arbitrary input $x$ , whose behaviour encodes whether $x \in K$ : typically "on any input $y$ , first simulate $φ_{x} (x)$ , and only if that halts do the thing that puts $P_{x}$ into $B$ ".
Invoke the $s$ - $m$ - $n$ theorem to make $x \mapsto ⌈ P_{x} ⌉$ a total computable function $f$ . This is the step that makes the construction legitimate rather than merely plausible; the definition of $\leq_{m}$ requires $f$ to be total and computable, never partial.
Verify both directions: $x \in K \Rightarrow f (x) \in B$ , and $x \in / K \Rightarrow f (x) \in / B$ . The second is where sloppy constructions fail, because a machine that "does nothing" must genuinely land outside $B$ .
Conclude $K \leq_{m} B$ , so $B$ is undecidable by Theorem Reduction transfers decidability and enumerability.

Example 6.33 (The non-emptiness problem). Let $NE = {e : W_{e} \neq = \emptyset}$ , the set of programs that halt on at least one input. Prove $K \leq_{m} NE$ , and deduce that $NE$ is undecidable.

Solution. Follow the recipe. Define the partial computable function of two arguments $θ (x, y) ≃ φ_{x} (x)$ , take an index $d$ for it, and set $f (x) = s_{1}^{1} (d, x)$ , which is total computable by the $s$ - $m$ - $n$ theorem. Then $φ_{f (x)} (y) ≃ φ_{x} (x)$ for all $y$ , so

W_{f (x)} = {N \emptyset if x \in K, if x \in / K .

Both directions are immediate from this: if $x \in K$ then $W_{f (x)} = N \neq = \emptyset$ , so $f (x) \in NE$ ; and if $x \in / K$ then the inner simulation never halts, so $φ_{f (x)}$ is defined nowhere, $W_{f (x)} = \emptyset$ , and $f (x) \in / NE$ . Hence $K \leq_{m} NE$ and $NE$ is undecidable.

Note that $NE$ is r.e.: dovetail the computations $φ_{e} (0), φ_{e} (1), \dots$ and halt if any of them halts. So $NE$ is another r.e. undecidable set, and by Theorem Complementation characterises decidability its complement — "this program halts on no input" — is not r.e. □□

Example 6.34 (Totality is not even r.e.). Let $TOT = {e : φ_{e} is total}$ . Show $K \leq_{m} TOT$ , so $TOT$ is undecidable, and show in addition that $TOT$ is not r.e.

Solution. The same $f$ works: $φ_{f (x)}$ is the constant function on all of $N$ when $x \in K$ , hence total, and the empty function when $x \in / K$ , hence not total. So $K \leq_{m} TOT$ and $TOT$ is undecidable.

For the stronger claim, reduce $\overline{K}$ instead. Define $ψ (x, y)$ to be $0$ if $φ_{x} (x)$ does not halt within $y$ steps, and undefined otherwise — a legitimate partial computable function, since the step test is decidable, and one whose domain is an initial segment of $N$ . By $s$ - $m$ - $n$ get a total computable $h$ with $φ_{h (x)} (y) ≃ ψ (x, y)$ . If $x \in / K$ then $φ_{x} (x)$ halts within no number of steps, so $φ_{h (x)} (y) = 0$ for every $y$ and $h (x) \in TOT$ . If $x \in K$ , say $φ_{x} (x)$ halts in exactly $s$ steps, then $φ_{h (x)} (y)$ is undefined for all $y \geq s$ , so $h (x) \in / TOT$ . Hence $\overline{K} \leq_{m} TOT$ , and since $\overline{K}$ is not r.e. by Corollary The complement of $K$ is not even r.e., Theorem Reduction transfers decidability and enumerability shows $TOT$ is not r.e. either. □□

Reduction also organises the r.e. sets into a hierarchy with a top.

Definition 6.35 ( $m$ -completeness). A set $B$ is $m$ -complete for the r.e. sets if $B$ is r.e. and $A \leq_{m} B$ for every r.e. $A$ .

Theorem 6.36 ( $K$ is $m$ -complete). $K$ is r.e., and $A \leq_{m} K$ for every r.e. set $A$ . Hence $K$ is $m$ -complete, and so is $K_{0}$ .

Proof. $K$ is r.e. as noted above. Let $A = W_{i}$ be r.e. Define the partial computable function of two arguments

θ (x, y) ≃ φ_{i} (x),

which ignores $y$ , and fix an index $d$ for it. By $s$ - $m$ - $n$ , $f (x) = s_{1}^{1} (d, x)$ is total computable and satisfies $φ_{f (x)} (y) ≃ φ_{i} (x)$ for all $y$ . In particular, taking $y = f (x)$ ,

f (x) \in K ⟺ φ_{f (x)} (f (x)) ↓ ⟺ φ_{i} (x) ↓ ⟺ x \in A .

So $f$ is a many-one reduction of $A$ to $K$ . Since $K \leq_{m} K_{0}$ via $x \mapsto ⟨ x, x ⟩$ , and $K_{0}$ is r.e., $K_{0}$ is $m$ -complete as well.∎

Corollary 6.37 (Undecidability by completeness). Every $m$ -complete set is undecidable, since $K$ is undecidable and reduces to it. Conversely, exhibiting a reduction $K \leq_{m} B$ for an r.e. $B$ shows $B$ is exactly as hard as the halting problem, not merely at least as hard.

Many-one reduction is not the only notion of relative difficulty, and it is deliberately restrictive: the translating function may consult $B$ only once, at the very end, and must accept its verdict unchanged. Allowing unrestricted use gives the coarser notion that governs the rest of the chapter.

Definition 6.38 (Oracle machines and Turing reducibility). An oracle machine with oracle $B \subseteq N$ is a Turing machine with an extra instruction "is $n \in B$ ? ", answered in one step and correctly. Write $Φ_{e}^{B}$ for the partial function computed by the $e$ -th oracle machine with oracle $B$ .

$A$ is Turing reducible to $B$ , written $A \leq_{T} B$ , if $χ_{A} = Φ_{e}^{B}$ for some $e$ — that is, $A$ is decidable by an algorithm allowed to ask membership questions about $B$ . If $A \leq_{T} B$ and $B \leq_{T} A$ , the sets are Turing equivalent, $A \equiv_{T} B$ .

Proposition 6.39 (Many-one is strictly finer than Turing). $A \leq_{m} B$ implies $A \leq_{T} B$ , and $A \leq_{T} B$ implies $\overline{A} \leq_{T} B$ . The converse of the first implication fails: $\overline{K} \leq_{T} K$ but $\overline{K} \neq \leq_{m} K$ .

Proof. If $f$ reduces $A$ to $B$ many-one, an oracle machine computes $f (x)$ , asks the oracle whether $f (x) \in B$ , and returns the answer; so $A \leq_{T} B$ . For the second claim, negate the output of the oracle machine deciding $A$ — a decision procedure can always be complemented, which is exactly what a semi-decision procedure cannot do.

$\overline{K} \leq_{T} K$ : with oracle $K$ we decide $x \in K$ and return the opposite answer. But $\overline{K} \neq \leq_{m} K$ : a many-one reduction $f$ of $\overline{K}$ to $K$ would make $\overline{K}$ r.e. by Theorem Reduction transfers decidability and enumerability, since $K$ is r.e., contradicting Corollary The complement of $K$ is not even r.e.∎

Remark. The asymmetry in that last proof is worth naming. Many-one reducibility respects the difference between "yes" and "no": it cannot flip an answer, so it can distinguish $K$ from $\overline{K}$ . Turing reducibility identifies them, because a decision procedure may negate its answer freely. That is why $\leq_{m}$ is the right tool for statements about r.e. sets and $\leq_{T}$ is the right tool for measuring absolute information content, which is the subject of the final section.

Exercises for §6.5 →

6.6Rice's Theorem and the Recursion Theorem

The reductions of the last section were each built by hand, and each looked much like the last. Rice's theorem explains why: every question about what a program computes, as opposed to how it is written, is undecidable unless it is trivial. It is the one theorem in the chapter that closes a whole class of questions at once.

Definition 6.40 (Index set). A set $P \subseteq N$ is an index set if membership depends only on the function computed:

φ_{i} = φ_{j} ⟹ (i \in P ⟺ j \in P) .

Equivalently, $P = {e : φ_{e} \in C}$ for some class $C$ of partial computable functions. An index set is trivial if it is $\emptyset$ or $N$ .

Index sets are exactly the semantic properties: they cannot distinguish two programs that behave identically, however differently they are written. A property like "the code of $M$ has an even number of states" is not an index set, since padding a machine changes the state count without changing its function.

Theorem 6.41 (Rice's theorem). Every non-trivial index set is undecidable. Equivalently: if $C$ is a class of partial computable functions that is neither empty nor all of them, then ${e : φ_{e} \in C}$ is undecidable.

Proof. Let $P$ be a non-trivial index set. Let $0$ denote the everywhere-undefined function, and let $e_{\emptyset}$ be an index for it (the machine that loops immediately on every input).

Case 1: $e_{\emptyset} \in / P$ . Since $P \neq = \emptyset$ , choose $e_{1} \in P$ , so $φ_{e_{1}}$ is some partial computable function in the class. Define the partial function of two arguments

θ (x, y) ≃ {φ_{e_{1}} (y) undefined if φ_{x} (x) ↓, otherwise,

realised by the algorithm. On input $(x, y)$ , first simulate $φ_{x} (x)$ using the universal machine; if and when that halts, simulate $φ_{e_{1}} (y)$ and return its value. This is partial computable, so it has an index $d$ , and by the $s$ - $m$ - $n$ theorem there is a total computable $f$ with $φ_{f (x)} (y) ≃ θ (x, y)$ for all $x, y$ .

Check both directions. If $x \in K$ then $φ_{x} (x) ↓$ , so the first simulation always completes and $φ_{f (x)} (y) ≃ φ_{e_{1}} (y)$ for every $y$ ; that is, $φ_{f (x)} = φ_{e_{1}}$ . As $P$ is an index set and $e_{1} \in P$ , we get $f (x) \in P$ . If $x \in / K$ then $φ_{x} (x) ↑$ , so the first simulation never completes and $φ_{f (x)} (y)$ is undefined for every $y$ ; that is, $φ_{f (x)} = 0 = φ_{e_{\emptyset}}$ . As $P$ is an index set and $e_{\emptyset} \in / P$ , we get $f (x) \in / P$ .

So $x \in K ⟺ f (x) \in P$ , i.e. $K \leq_{m} P$ , and by Theorem Reduction transfers decidability and enumerability together with Theorem Undecidability of the halting problem, $P$ is undecidable.

Case 2: $e_{\emptyset} \in P$ . Then $e_{\emptyset} \in / \overline{P}$ , and $\overline{P}$ is again an index set — the defining implication is preserved under complement — and again non-trivial, since $P \neq = N$ gives $\overline{P} \neq = \emptyset$ and $P \neq = \emptyset$ gives $\overline{P} \neq = N$ . Case 1 applies to $\overline{P}$ , so $\overline{P}$ is undecidable; and a set is decidable exactly when its complement is, by Proposition Closure properties. Hence $P$ is undecidable.

Both cases are covered, since $e_{\emptyset}$ either does or does not belong to $P$ .∎

Intuition. Read the construction as a behaviour swap. The program $f (x)$ is built so that its behaviour is $φ_{e_{1}}$ — a behaviour inside the property — when $φ_{x} (x)$ halts, and no behaviour at all when it does not. Any decider for the property would therefore be reporting, in disguise, whether $φ_{x} (x)$ halts. Nothing about the property was used except that some program has it and some program does not; that is why the theorem is so sweeping, and also why triviality is the only escape.

Corollary 6.42 (A catalogue of undecidable questions). Each of the following is an undecidable property of a given program $e$ , because each defines a non-trivial index set: $φ_{e}$ is total; $W_{e}$ is empty; $W_{e}$ is finite; $W_{e}$ is infinite; $W_{e} = N$ ; $φ_{e} (0) = 42$ ; $φ_{e}$ is a constant function; $W_{e}$ is decidable; $φ_{e}$ agrees with a fixed partial computable function $ψ$ .

Pitfall. Rice's theorem applies only to index sets, and to non-trivial ones. Three common misapplications:

"Does $M$ halt on the empty tape within $100$ steps?" is decidable — simulate for $100$ steps. It is not an index set, because two machines computing the same function can differ in speed.
"Does the code of $M$ contain more than seven states?" is decidable by inspection; again not an index set, by padding.
"Is $φ_{e}$ partial computable?" is trivially true of every $e$ , so the index set is $N$ and the question is decidable — the answer is always yes.

Rice also does not say the property is non-r.e. Some non-trivial index sets are r.e. ( $NE$ , from the previous section, is) and some are not ( $TOT$ is not). Undecidable and non-r.e. are different claims, and Rice gives only the first.

Theorem 6.43 (Rice-Shapiro, which r.e. index sets look like). Let $C$ be a class of partial computable functions such that $P = {e : φ_{e} \in C}$ is r.e. Then for every partial computable $ψ$ ,

ψ \in C ⟺ some finite sub-function σ \subseteq ψ lies in C .

In words: an r.e. semantic property must be decided by a finite amount of the function's behaviour, and must be preserved when more behaviour is added.

Proof. Sketch, giving the easy direction in full and the idea of the other. If some finite $σ \subseteq ψ$ lies in $C$ , then the "monotone" half asserts $ψ \in C$ ; this half is proved by a reduction from $\overline{K}$ of the same shape as in the $TOT$ example, using a machine that computes $σ$ and then extends it to $ψ$ only while $φ_{x} (x)$ has not yet halted. If no finite sub-function of $ψ$ lies in $C$ but $ψ$ does, a symmetric construction reduces $\overline{K}$ to $P$ , contradicting that $P$ is r.e. The compressed step in both halves is the verification that the approximating machines are uniformly constructible, which is $s$ - $m$ - $n$ applied exactly as in the proof of Rice's theorem.

The theorem immediately explains the catalogue above: " $φ_{e}$ is total" fails the finiteness condition, since no finite sub-function is total, so $TOT$ is not r.e. — recovering by a general principle what the previous section proved by hand.∎

Rice's theorem was proved by reduction. There is a second route to it, through a theorem about self-reference which is worth having in its own right: it is the formal statement that a program can be given access to its own code.

Theorem 6.44 (Kleene's recursion theorem). For every total computable $f$ there is an $n$ with

φ_{n} = φ_{f (n)} .

Such an $n$ is called a fixed point of $f$ . In the stronger parametrised form: for every partial computable $ψ (x, y)$ there is an $n$ with $φ_{n} (y) ≃ ψ (n, y)$ for all $y$ — a program may use its own index.

Proof. Sketch, complete in structure with one routine $s$ - $m$ - $n$ step left implicit. Define a partial computable function of two arguments by

θ (x, y) ≃ φ_{φ_{x} (x)} (y),

meaning: compute $φ_{x} (x)$ ; if it converges to a value $v$ , run $φ_{v} (y)$ . By $s$ - $m$ - $n$ there is a total computable $g$ with $φ_{g (x)} (y) ≃ θ (x, y)$ , so $φ_{g (x)} = φ_{φ_{x} (x)}$ whenever $φ_{x} (x) ↓$ . Now let $f$ be total computable and let $v$ be an index for the total computable composition $f \circ g$ , so $φ_{v} (x) = f (g (x))$ for all $x$ , and put $n = g (v)$ . Then

φ_{n} = φ_{g (v)} = φ_{φ_{v} (v)} = φ_{f (g (v))} = φ_{f (n)},

where the second equality uses the displayed property of $g$ at $x = v$ , legitimate because $φ_{v} (v) = f (g (v))$ is defined. The implicit step is the construction of $g$ itself, which is the same splicing argument as in Theorem The $s$ - $m$ - $n$ theorem.∎

Intuition. The recursion theorem is the reason self-referential programs are not paradoxical but routine. A quine — a program that prints its own source — is the fixed point of the function "given a program $p$ , return the program that prints $p$ ". Recursive definitions in programming languages are the same phenomenon: let rec is a fixed-point operator, and the theorem says the fixed point always exists and is computable. The diagonalisation of the halting proof and the self-application here are the same manoeuvre used with opposite intent — there to derive a contradiction, here to construct an object.

Example 6.45 (Rice's theorem again, from the recursion theorem). Derive Rice's theorem from Theorem Kleene's recursion theorem instead of from a reduction.

Solution. Let $P$ be a non-trivial index set and suppose it were decidable, with total decider $D$ . Non-triviality gives indices $a \in P$ and $b \in / P$ . Define

f (x) = {b a if D (x) = 1, i.e. x \in P, if D (x) = 0, i.e. x \in / P .

Since $D$ is total and computable, so is $f$ . By the recursion theorem $f$ has a fixed point $n$ with $φ_{n} = φ_{f (n)}$ , and since $P$ is an index set this gives $n \in P ⟺ f (n) \in P$ .

But $f$ was built to violate exactly that: if $n \in P$ then $f (n) = b \in / P$ , and if $n \in / P$ then $f (n) = a \in P$ . Both cases contradict the displayed equivalence, so $D$ cannot exist.

The two proofs differ in flavour: the reduction proof shows how hard $P$ is, yielding $K \leq_{m} P$ , whereas this one shows only that $P$ is undecidable — but it does so in six lines, and it never mentions the halting problem. □□

Exercises for §6.6 →

6.7The Arithmetical Hierarchy and Turing Degrees

Undecidability is not a single condition. $\overline{K}$ is harder than $K$ in a precise sense, $TOT$ is harder than both, and there is an unbounded ladder above them. Two measuring instruments make this precise: a syntactic one counting quantifier alternations, and a computational one counting oracles.

Definition 6.46 (The arithmetical hierarchy). A relation is $Σ_{0}^{0} = Π_{0}^{0} = Δ_{0}^{0}$ if it is definable by a formula of arithmetic all of whose quantifiers are bounded, of the form $(\forall i < t)$ or $(\exists i < t)$ ; every such relation is decidable. For $n \geq 0$ , a set $A \subseteq N$ is

$Σ_{n + 1}^{0}$ if $A = {x : \exists y R (x, y)}$ for some $Π_{n}^{0}$ relation $R$ ;
$Π_{n + 1}^{0}$ if $A = {x : \forall y R (x, y)}$ for some $Σ_{n}^{0}$ relation $R$ ;
$Δ_{n}^{0}$ if it is both $Σ_{n}^{0}$ and $Π_{n}^{0}$ .

The superscript $0$ records that the quantifiers range over numbers, not sets; it is often dropped. $A$ is $Σ_{n}^{0}$ if and only if $\overline{A}$ is $Π_{n}^{0}$ , directly from the definition and the duality of $\exists$ and $\forall$ .

Notation. Consecutive like quantifiers collapse: $\exists y_{1} \exists y_{2} R$ is $\exists z R^{'}$ with $z = ⟨ y_{1}, y_{2} ⟩$ and $R^{'}$ decoding the pair, which costs only bounded quantifiers. So the level of a set is the number of alternations in the simplest formula defining it, and adding a dummy quantifier is always allowed: $Σ_{n}^{0} \cup Π_{n}^{0} \subseteq Δ_{n + 1}^{0}$ .

Theorem 6.47 (Post's normal-form theorem). A set $A \subseteq N$ is recursively enumerable if and only if it is $Σ_{1}^{0}$ .

Proof. ( $\Leftarrow$ ) Suppose $A = {x : \exists y R (x, y)}$ with $R$ decidable. The machine that on input $x$ tests $R (x, 0), R (x, 1), R (x, 2), \dots$ in turn and halts at the first success has domain exactly $A$ : it halts when a witness exists and searches forever when none does. So $A$ is the domain of a partial computable function, i.e. r.e.

( $\Rightarrow$ ) Suppose $A = W_{e}$ . By Theorem Kleene normal form, and equivalence with Turing computability, $φ_{e} (x) ↓$ exactly when some $s$ codes a halting computation of $M_{e}$ on $x$ , and $T (e, x, s)$ is primitive recursive, hence decidable. So

A = {x : \exists s T (e, x, s)},

which is $Σ_{1}^{0}$ .∎

Corollary 6.48 (Decidable equals $Δ_{1}^{0}$ ). $A$ is decidable if and only if $A$ is $Δ_{1}^{0}$ .

Proof. If $A$ is decidable then $A$ and $\overline{A}$ are both r.e. by Theorem Complementation characterises decidability, so both are $Σ_{1}^{0}$ by Post's normal-form theorem; $\overline{A} \in Σ_{1}^{0}$ means $A \in Π_{1}^{0}$ , so $A \in Δ_{1}^{0}$ . Conversely if $A$ is $Σ_{1}^{0}$ and $Π_{1}^{0}$ then $A$ and $\overline{A}$ are both $Σ_{1}^{0}$ , hence both r.e., hence $A$ is decidable by the same theorem.∎

Example 6.49 (Reading the level off the definition). Classify $K$ , $\overline{K}$ , $TOT$ and $FIN = {e : W_{e} is finite}$ in the hierarchy.

Solution. Write everything in terms of the decidable predicate $H (e, x, s)$ : " $φ_{e} (x)$ halts within $s$ steps".

$K = {e : \exists s H (e, e, s)}$ is $Σ_{1}^{0}$ , and it is not $Π_{1}^{0}$ , since a $Π_{1}^{0}$ set has $Σ_{1}^{0}$ complement and $\overline{K}$ is not r.e. So $K$ is properly $Σ_{1}^{0}$ , and dually $\overline{K}$ is properly $Π_{1}^{0}$ .

$TOT = {e : \forall x \exists s H (e, x, s)}$ : the inner part $\exists s H$ is $Σ_{1}^{0}$ , and one universal quantifier in front makes it $Π_{2}^{0}$ . It is in fact properly $Π_{2}^{0}$ — no $Σ_{2}^{0}$ definition exists — which is a sharpening of the earlier fact that it is not r.e.

$FIN = {e : \exists b \forall x (x > b \to \forall s \neg H (e, x, s))}$ , an $\exists$ over a $Π_{1}^{0}$ matrix, hence $Σ_{2}^{0}$ ; it is properly so, and note $FIN = \overline{INF}$ with $INF$ properly $Π_{2}^{0}$ . Counting the alternations in the plainest definition is almost always the right first move; proving that the count cannot be lowered is the harder half and needs the hierarchy theorem below. □□

Figure 6.50. The first levels of the arithmetical hierarchy. Each line is an inclusion, upwards.

Δ_{1}^{0}

is the decidable sets,

Σ_{1}^{0}

the r.e. sets and

Π_{1}^{0}

their complements;

K

sits properly in

Σ_{1}^{0}

and

TOT

properly in

Π_{2}^{0}

. Every inclusion drawn is strict.

The computational instrument is the oracle, and iterating it produces exactly the same ladder.

Definition 6.51 (Turing degrees and the jump). The relation $\equiv_{T}$ of Turing equivalence is an equivalence relation on $P (N)$ ; its classes are the Turing degrees, written $de g (A)$ , and $\leq_{T}$ induces a partial order on them. The degree of the decidable sets is written $0$ ; it is the least degree.

The Turing jump of $A$ is

A^{'} = {e : Φ_{e}^{A} (e) ↓},

the halting problem relativised to the oracle $A$ . Write $A^{(0)} = A$ and $A^{(n + 1)} = (A^{(n)})^{'}$ , so $\emptyset^{'} \equiv_{T} K$ and $0^{(n)} = de g (\emptyset^{(n)})$ .

Theorem 6.52 (The jump is a strict increase). For every $A \subseteq N$ : $A^{'}$ is r.e. in $A$ ; $A \leq_{T} A^{'}$ ; and $A^{'} \neq \leq_{T} A$ . Hence $A <_{T} A^{'}$ strictly, and

\emptyset <_{T} \emptyset^{'} <_{T} \emptyset^{''} <_{T} \dots

is a strictly increasing chain of degrees, so there is no hardest undecidable problem.

Proof. $A^{'}$ is r.e. in $A$ : the oracle machine that on input $e$ simulates $Φ_{e}^{A} (e)$ , consulting the oracle whenever the simulation does, halts exactly on $A^{'}$ .

$A \leq_{T} A^{'}$ : for each $n$ let $j (n)$ be an index of the oracle machine that, on any input, asks the oracle whether $n \in A$ and halts if the answer is yes, looping otherwise. The map $n \mapsto j (n)$ is total computable by relativised $s$ - $m$ - $n$ , and $n \in A ⟺ j (n) \in A^{'}$ . So $A \leq_{m} A^{'}$ , hence $A \leq_{T} A^{'}$ .

$A^{'} \neq \leq_{T} A$ : this is the halting proof relativised, and every step survives the addition of the oracle. Suppose $χ_{A^{'}}$ were computable from $A$ . Then the partial function that on input $x$ decides whether $x \in A^{'}$ using the oracle, outputs $0$ if the answer is no, and loops if the answer is yes, is partial computable in $A$ , hence equals $Φ_{i}^{A}$ for some $i$ . Then $i \in A^{'} ⟺ Φ_{i}^{A} (i) ↓ ⟺ i \in / A^{'}$ , a contradiction.

Applying the three facts to $\emptyset, \emptyset^{'}, \emptyset^{''}, \dots$ in turn gives the chain, and each step is strict.∎

Theorem 6.53 (Post's theorem). For every $n \geq 0$ : a set $A$ is $Σ_{n + 1}^{0}$ if and only if $A$ is r.e. in $\emptyset^{(n)}$ ; and $A$ is $Δ_{n + 1}^{0}$ if and only if $A \leq_{T} \emptyset^{(n)}$ . Moreover $\emptyset^{(n)}$ is $m$ -complete for $Σ_{n}^{0}$ when $n \geq 1$ .

Proof. Sketch. The case $n = 0$ is Post's normal-form theorem together with Corollary Decidable equals $Δ_{1}^{0}$ . The induction step in one direction relativises the normal-form proof: a $Σ_{n + 1}^{0}$ set is $\exists y$ over a $Π_{n}^{0}$ matrix, and by the induction hypothesis the matrix is decidable with oracle $\emptyset^{(n)}$ , so searching for a witness is a semi-decision procedure with that oracle. The other direction relativises the $T$ -predicate construction, writing "the oracle computation halts" as an existential over a predicate decidable in $\emptyset^{(n)}$ and then unwinding the oracle queries into the extra quantifiers supplied by the induction hypothesis. The step compressed is that unwinding, which needs the fact that oracle queries can be bundled into a single quantifier using a finite use of the oracle.∎

Corollary 6.54 (The hierarchy is proper). For every $n \geq 1$ , $Σ_{n}^{0} \neq = Π_{n}^{0}$ and $Δ_{n}^{0} ⊊ Σ_{n}^{0}$ . In particular the arithmetical hierarchy does not collapse at any level.

Proof. By Post's theorem $\emptyset^{(n)}$ is $Σ_{n}^{0}$ . If $Σ_{n}^{0}$ were closed under complement we would have $\emptyset^{(n)} \in Π_{n}^{0}$ , hence $\emptyset^{(n)} \in Δ_{n}^{0}$ , hence by Post's theorem $\emptyset^{(n)} \leq_{T} \emptyset^{(n - 1)}$ — contradicting Theorem The jump is a strict increase, which makes the inequality strict. So $Σ_{n}^{0} \neq = Π_{n}^{0}$ , and since $Δ_{n}^{0} = Σ_{n}^{0} \cap Π_{n}^{0}$ the second inclusion is strict too.∎

Intuition. The two instruments measure the same thing from opposite sides. Syntactically, each new quantifier alternation is a new level; computationally, each new jump is a new oracle. Post's theorem says the counts agree: $n$ alternations of quantifier is exactly $n$ applications of "solve the halting problem for the previous level". $TOT$ being $Π_{2}^{0}$ means precisely that with a halting oracle you could semi-decide its complement but not decide it, and would need a second jump to settle it.

Remark (Post's problem and what lies between). Every r.e. set $A$ satisfies $\emptyset \leq_{T} A \leq_{T} \emptyset^{'}$ , and the classical examples — $K$ , $K_{0}$ , $NE$ — are all of degree exactly $0^{'}$ . Post asked in 1944 whether there is an r.e. set of degree strictly between $0$ and $0^{'}$ . Friedberg and Muchnik answered yes, independently, in 1956-57, constructing two r.e. sets $A, B$ with $A \neq \leq_{T} B$ and $B \neq \leq_{T} A$ ; both then have intermediate degree. The proof introduced the priority method, in which infinitely many conflicting requirements are met by assigning them priorities and allowing high-priority requirements to injure the work done for lower ones only finitely often. That method is the engine of modern recursion theory and is well beyond this chapter, but the statement is worth carrying: the structure of the r.e. degrees is rich, not a two-element chain.

Remark (Where Kolmogorov complexity fits). A closely related uncomputability runs through the length of the shortest program producing a given string, the Kolmogorov complexity $C (x)$ . That function is not computable, essentially by a diagonal argument of the same family as the one above, and the set ${x : C (x) \geq ∣ x ∣}$ of incompressible strings is not r.e. although its complement is. The chapter Algorithmic Information in information theory develops that theory — invariance, incompressibility, the connection to entropy and Chaitin's constant — and it is the right place to look for the string-by-string version of everything this chapter says about sets and functions.

Exercises for §6.7 →

Common Mistakes

Confusing undecidable with uncomputable-in-general: Undecidability of halting does not mean nothing can be computed. Almost all the mathematics you use daily is computable; what fails is one uniform question about arbitrary programs.
Applying Rice's theorem to syntax or to resource bounds: "Does the code have an even number of states?" and "does $M$ halt within $100$ steps?" are both decidable. Rice needs an index set — a property invariant under changes of program that preserve behaviour — and neither of these is one.
Reducing in the wrong direction: To prove $B$ undecidable you need $K \leq_{m} B$ , translating halting instances into $B$ -instances. Producing a reduction $B \leq_{m} K$ instead proves nothing about $B$ .
Treating a partial reduction function as a reduction: The $f$ in $A \leq_{m} B$ must be total computable. A construction that only sometimes returns a program is not a reduction; this is exactly what the $s$ - $m$ - $n$ theorem is invoked to repair.
Equating r.e. with decidable: A set can be listable without being decidable — $K$ is the standing example. The listing must be in increasing order before you may conclude decidability.
Equating recursive with primitive recursive: The primitive recursive functions are a proper subclass of the total recursive ones; Ackermann's function is total and computable but not primitive recursive.
Reading the Church-Turing thesis as a theorem: It equates a formal class with an informal notion and so is not provable, only supportable — and refutable, in principle, by a physically realisable counterexample.
Believing undecidability forbids tools: Compilers, static analysers and termination checkers all attack undecidable questions successfully, by being sound and incomplete: they are allowed to answer "don't know".
Confusing halting with speed: A machine that halts on every input may still take astronomically long. Computability says nothing about running time; that is the business of complexity theory.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

Practice this chapter