42.04.02 · mathematical-logic / computability-degrees

The Halting Problem, Undecidability, and the Recursion Theorem

shipped3 tiersLean: none

Anchor (Master): Soare 2016 *Turing Computability: Theory and Applications* (Springer) Ch. 2-4 and the historical notes (the diagonal at $K$, $m$-completeness of $K$, Rice and Rice-Shapiro, the recursion theorem and its iterates, undecidable problems beyond halting); Rogers 1967 *Theory of Recursive Functions and Effective Computability* (McGraw-Hill) Ch. 7-11 (reducibilities, index sets, Rice's theorem, the recursion theorem and the second recursion theorem); Odifreddi 1989 *Classical Recursion Theory, Volume I* (North-Holland) Ch. II-III (the s-m-n / recursion-theorem package, Rice-Shapiro, productive and creative sets, the relation of $K$ to first-order undecidability)

Intuition Beginner

Some questions about computer programs sound like they should have a mechanical answer, yet none exists. The most famous one is the halting question: given a program and an input, will the program eventually stop, or will it loop forever? You might hope for a master checker — a program that reads any other program, looks at its input, and prints "stops" or "loops" without ever being wrong and without itself running forever. The surprising fact of this unit is that no such master checker can exist, and the reason is a single, very short argument.

The argument is a kind of self-reference trap. Suppose the master checker existed. Then you could build a mischief program that first asks the checker, "what will I do when I am run on my own code?" — and then deliberately does the opposite. If the checker says this program stops, the mischief program loops; if the checker says it loops, the mischief program stops. Run the mischief program on its own code and the checker is wrong no matter what it says. Since a correct checker cannot be wrong, the checker cannot exist.

That one trick — feed a thing its own description and flip the answer — is the seed of a whole landscape. Once you know the halting question has no mechanical answer, you can show that many other questions inherit the same fate by quietly smuggling the halting question inside them. A rough rule emerges: almost any interesting yes-or-no question about what a program computes (not how it is written) has no general decision procedure.

There is a hopeful twin to all this. The same self-reference that traps the checker can be used on purpose. You can always write a program that builds and prints its own source code, and more generally a program that is allowed to refer to itself while it runs. Self-reference, handled carefully, is not a paradox but a tool.

Visual Beginner

The diagonal trap, drawn as a table. Imagine listing every program down the side and every input across the top, and in each cell writing whether that program stops on that input. The mischief program is built to disagree with the diagonal of this table — the cells where a program is run on its own number — so it cannot appear anywhere in the list.

            input = program number
            P0    P1    P2    P3   ...
        +-----------------------------
   P0   | STOP  loop  STOP  loop      <- on the diagonal: STOP
   P1   | loop  loop  STOP  STOP      <- on the diagonal: loop
   P2   | STOP  STOP  loop  loop      <- on the diagonal: loop
   P3   | STOP  loop  loop  STOP      <- on the diagonal: STOP
   ...  |
        diagonal reads:  STOP loop loop STOP ...

   mischief program D, run on input n, does the OPPOSITE of cell (Pn, n):
        diagonal:        STOP  loop  loop  STOP ...
        D does instead:  loop  STOP  STOP  loop ...

   Could D be some row Pk in the table?
        At column k, D must differ from Pk's diagonal cell.
        So D's row disagrees with every row at its own column.
        D is not in the list. Contradiction.

Read it as a staring contest between D and the table. Whatever row you guess D is, look at that row's diagonal cell: D was defined to do the opposite there. So D matches no row. Yet if a halting checker existed, D would be a perfectly good program and would have a row. The table cannot hold D, so the checker cannot exist.

program run on its own number	diagonal says	`D` is built to do
`P0` on `0`	STOP	loop
`P1` on `1`	loop	STOP
`P2` on `2`	loop	STOP
`P3` on `3`	STOP	loop

The flip down the diagonal is the whole proof: D is everywhere different from the list, so it is not on the list.

Worked example Beginner

We pin down the contradiction with one concrete program, using only addition and "ask the checker." Pretend a perfect halting checker $H$ exists: given a program $P$ and an input $n$ , $H (P, n)$ returns $1$ if $P$ stops on $n$ and $0$ if $P$ loops on $n$ , always correctly and always quickly.

Step 1. Build a new program $D$ . On input $n$ (a program number), $D$ runs $H$ on the pair "program number $n$ , input $n$ " — that is, it asks whether program $n$ stops when fed its own number.

Step 2. Make $D$ contrary. If $H$ answers $1$ (program $n$ stops on $n$ ), then $D$ enters a loop and never stops. If $H$ answers $0$ (program $n$ loops on $n$ ), then $D$ stops immediately.

Step 3. Give $D$ its own number. Say $D$ is program number $d$ . Run $D$ on input $d$ . Inside, $D$ asks $H$ whether program $d$ stops on $d$ — but program $d$ is $D$ , so this asks whether $D$ stops on $d$ , the very thing we are running.

Step 4. Watch both answers fail. If $H$ says $D$ stops on $d$ , then by Step 2 $D$ loops on $d$ — so $H$ was wrong. If $H$ says $D$ loops on $d$ , then by Step 2 $D$ stops on $d$ — so $H$ was wrong again. Either way the perfect checker is wrong on this one input.

What this tells us: a checker that is right on every program-and-input pair contradicts itself the moment you feed it $D$ on $d$ . There is no escape value for $H$ to return. So a perfect, always-halting halting checker is impossible — the halting question has no general mechanical answer.

Check your understanding Beginner

Formal definition Intermediate+

Fix the standard enumeration ${φ_{e}}_{e \in N}$ of unary partial computable functions, the universal function $U (e, x) ≃ φ_{e} (x)$ , and the s-m-n functions $s_{n}^{m}$ from 42.04.01. Write $φ_{e} (x) ↓$ when the computation halts (the value is defined) and $φ_{e} (x) ↑$ when it diverges; $≃$ denotes Kleene equality (both sides defined and equal, or both undefined). The halting set (the diagonal halting set) is $$ K = {, e : \varphi_e(e)!\downarrow ,}, $$ and the general halting set is $K_{0} = {⟨ e, x ⟩ : φ_{e} (x) ↓}$ , using a computable pairing $⟨ \cdot, \cdot ⟩$ . A set $A \subseteq N$ is computable if its characteristic function $χ_{A}$ is computable, and computably enumerable (c.e.) if it is the domain of a partial computable function ^{[Soare Ch. 2]}.

For sets $A, B \subseteq N$ , $A$ is many-one reducible to $B$ , written $A \leq_{m} B$ , if there is a total computable $f$ with $$ x \in A \iff f(x) \in B \qquad \text{for all } x. $$ The relation $\leq_{m}$ is reflexive and transitive; $A \equiv_{m} B$ means $A \leq_{m} B \leq_{m} A$ . A c.e. set $C$ is $m$ -complete if $A \leq_{m} C$ for every c.e. $A$ . Many-one reducibility transports decidability downward: if $A \leq_{m} B$ and $B$ is computable then $A$ is computable, and if $A \leq_{m} B$ and $B$ is c.e. then $A$ is c.e. The contrapositive is the working tool — to show $A$ undecidable, reduce a known-undecidable set (typically $K$ ) to it.

An index set is a set $I \subseteq N$ that respects the functions computed, not the programs: $φ_{a} = φ_{b} ⟹ (a \in I ⟺ b \in I)$ . Equivalently $I$ is the set of indices of the c.e. sets (or partial functions) lying in some class $C$ of c.e. sets, $I = {e : W_{e} \in C}$ where $W_{e} = dom (φ_{e})$ . The two index sets $\emptyset$ and $N$ correspond to the empty class and the class of all c.e. sets; every other index set encodes a property held by some but not all c.e. sets. A fixed point of a total computable $f$ is an index $n$ with $φ_{n} = φ_{f (n)}$ .

Counterexamples to common slips Intermediate+

" $K$ is uncomputable because it is infinite or complicated." Size and apparent complexity are irrelevant: $K$ is c.e., so it is the range of a computable function and can be listed. What fails is deciding non-membership — its complement $\overline{K}$ is not even c.e. Uncomputability is the asymmetry between $K$ and $\overline{K}$ , not bulk.
" $A \leq_{m} B$ means $A$ is a subset of $B$ ." It means a computable $f$ pulls membership in $A$ back from membership in $B$ ; $f$ need not be injective, monotone, or onto, and $A, B$ may be disjoint. The reduction is a translation of questions, not an inclusion of sets.
"Rice's theorem says every property of programs is undecidable." It governs extensional properties — properties of the computed function, i.e. index sets. Properties of the syntax ("does the program have more than ten states?", "does it ever print symbol $7$ in its first step?") can be perfectly decidable. The hypothesis " $I$ is an index set" is doing real work.
"The recursion theorem gives a fixed value, a number $n$ with $f (n) = n$ ." It gives a fixed point up to the computed function: $φ_{n} = φ_{f (n)}$ , an equality of programs' behaviour, not $f (n) = n$ . The transformation $f$ may move every index; the theorem only guarantees one index whose program is unchanged in meaning.

Key theorem with proof Intermediate+

The signature result is that $K$ is the simplest possible undecidable set: c.e., and maximally so under $\leq_{m}$ . Everything downstream — Rice's theorem, the undecidability of totality and emptiness, Church's theorem — is a reduction from $K$ .

Theorem (the halting set is c.e. and $m$ -complete). The set $K = {e : φ_{e} (e) ↓}$ is computably enumerable but not computable. Moreover $K$ is $m$ -complete: for every c.e. set $A$ , $A \leq_{m} K$ .

Proof. $K$ is c.e. because $K = dom (ψ)$ for the partial computable $ψ (e) ≃ U (e, e)$ : running the universal machine on $(e, e)$ halts exactly when $φ_{e} (e) ↓$ .

$K$ is not computable. Suppose $χ_{K}$ were computable. Define $$ g(e) \simeq \begin{cases} \varphi_e(e) + 1 & \text{if } e \in K, \ 0 & \text{if } e \notin K. \end{cases} $$ Since $χ_{K}$ is computable and $U$ supplies $φ_{e} (e)$ on $K$ , $g$ is total computable, so $g = φ_{e_{0}}$ for some index $e_{0}$ . Evaluate at $e_{0}$ . If $e_{0} \in K$ then $g (e_{0}) = φ_{e_{0}} (e_{0}) + 1 = g (e_{0}) + 1$ , impossible. If $e_{0} \in / K$ then $φ_{e_{0}} (e_{0}) ↑$ , yet $g (e_{0}) = 0$ is defined and $g = φ_{e_{0}}$ forces $φ_{e_{0}} (e_{0}) ↓$ , a contradiction. Hence $χ_{K}$ is not computable.

For $m$ -completeness, let $A$ be c.e., say $A = dom (φ_{a})$ . Consider the partial computable function of two arguments $θ (x, y) ≃ φ_{a} (x)$ — it ignores $y$ and runs $φ_{a}$ on $x$ . Let $c$ be an index with $φ_{c}^{(2)} = θ$ . By the s-m-n theorem there is a total computable $f (x) = s_{1}^{1} (c, x)$ with $φ_{f (x)} (y) ≃ φ_{c}^{(2)} (x, y) ≃ φ_{a} (x)$ for all $y$ . Thus $φ_{f (x)}$ is the everywhere-defined-constant or everywhere-undefined function according as $φ_{a} (x) ↓$ or $↑$ . In particular $φ_{f (x)} (f (x)) ↓ ⟺ φ_{a} (x) ↓ ⟺ x \in A$ , so $x \in A ⟺ f (x) \in K$ . Hence $A \leq_{m} K$ . $□$

Bridge. This theorem is the foundational reason undecidability is not a scattered collection of accidents but a single phenomenon: $K$ sits at the top of the c.e. sets under $\leq_{m}$ , so any problem to which $K$ reduces is undecidable, and any c.e. problem reduces to $K$ . The diagonal that defeats $χ_{K}$ is exactly the self-application $φ_{e} (e)$ the universal machine of 42.04.01 makes available — this is exactly the construction the recursion theorem will run forwards instead of for contradiction. The reduction technique builds toward Rice's theorem, where $K$ is reduced into an arbitrary extensional property, and it appears again in the undecidability of first-order validity, where $K$ is reduced into provability (Church's theorem, cross-ref 42.01.10 pending). The central insight is that $m$ -completeness packages "as hard as the halting problem" into a transitive relation, so putting these together one reduction from $K$ certifies an entire family of undecidable questions at once.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Show that the general halting set $K_{0} = {⟨ e, x ⟩ : φ_{e} (x) ↓}$ satisfies $K \leq_{m} K_{0}$ and $K_{0} \leq_{m} K$ , so $K \equiv_{m} K_{0}$ .

Hint

For $K \leq_{m} K_{0}$ map $e \mapsto ⟨ e, e ⟩$ . For $K_{0} \leq_{m} K$ use s-m-n to turn a pair into a single self-halting index.

Answer

$K \leq_{m} K_{0}$ : the map $e \mapsto ⟨ e, e ⟩$ is computable and $e \in K ⟺ φ_{e} (e) ↓ ⟺ ⟨ e, e ⟩ \in K_{0}$ . For $K_{0} \leq_{m} K$ : define $θ (⟨ e, x ⟩, y) ≃ φ_{e} (x)$ (ignoring $y$ ), with index $c$ , and set $f (⟨ e, x ⟩) = s_{1}^{1} (c, ⟨ e, x ⟩)$ by s-m-n, so $φ_{f (⟨ e, x ⟩)} (y) ≃ φ_{e} (x)$ for all $y$ . Then $φ_{f (⟨ e, x ⟩)} (f (⟨ e, x ⟩)) ↓ ⟺ φ_{e} (x) ↓ ⟺ ⟨ e, x ⟩ \in K_{0}$ , so $⟨ e, x ⟩ \in K_{0} ⟺ f (⟨ e, x ⟩) \in K$ . Both maps are total computable, giving $K \equiv_{m} K_{0}$ . Rubric: full credit for the diagonal embedding one way and the s-m-n constant-function construction the other.

Exercise 4 (medium, symbolic).

Prove the halting problem for inputs $H_{e} = {x : φ_{e} (x) ↓}$ can be the empty set, all of $N$ , or a properly intermediate c.e. set, and explain why "is $H_{e} = N$ ?" (the totality question) is therefore not settled by examining $e$ syntactically.

Hint

Exhibit three indices: a never-halting machine, a halt-always machine, and one halting exactly on $K$ .

Answer

Take $e_{\emptyset}$ computing the everywhere-divergent function (an immediate infinite loop): $H_{e_{\emptyset}} = \emptyset$ . Take $e_{N}$ computing the constant $0$ : $H_{e_{N}} = N$ . Take $e_{K}$ an index with $dom (φ_{e_{K}}) = K$ (possible since $K$ is c.e.): $H_{e_{K}} = K$ , a c.e. set that is neither empty nor all of $N$ nor computable. The domain of $φ_{e}$ can thus be any c.e. set, so reading off $dom (φ_{e})$ from $e$ would decide arbitrary c.e. membership; in particular deciding $H_{e} = N$ would decide totality, treated in the Advanced section as undecidable. Rubric: full credit for the three explicit indices and the observation that the domain ranges over all c.e. sets.

Exercise 6 (hard, symbolic).

Prove Rice's theorem: if $I$ is an index set with $I \neq = \emptyset$ and $I \neq = N$ , then $K \leq_{m} I$ or $K \leq_{m} \overline{I}$ ; conclude $I$ is undecidable.

Hint

Let $\emptyset$ -program have index $e_{\emptyset}$ . Arrange the reduction so that the target function is a fixed "good" function when $x \in K$ and the empty function when $x \in / K$ .

Answer

Let $e_{\emptyset}$ compute the everywhere-undefined function $\emptyset$ . Since $I$ is a non-empty, non-full index set, either $e_{\emptyset} \in / I$ or $e_{\emptyset} \in I$ ; treat $e_{\emptyset} \in / I$ (else replace $I$ by $\overline{I}$ , also an index set, and prove $K \leq_{m} \overline{I}$ ). As $I \neq = \emptyset$ pick $b \in I$ , computing some $φ_{b}$ . Define $θ (x, y) ≃ φ_{b} (y)$ if $x \in K$ , undefined otherwise; concretely $θ (x, y) ≃ (run φ_{x} (x); then output φ_{b} (y))$ , partial computable. Let $c$ index $θ$ and put $f (x) = s_{1}^{1} (c, x)$ , so $φ_{f (x)} = φ_{b}$ if $x \in K$ and $φ_{f (x)} = \emptyset$ if $x \in / K$ . Since $I$ is an index set, $x \in K ⟹ f (x) \in I$ (as $φ_{f (x)} = φ_{b}$ , $b \in I$ ) and $x \in / K ⟹ f (x) \in / I$ (as $φ_{f (x)} = \emptyset$ , $e_{\emptyset} \in / I$ ). Thus $x \in K ⟺ f (x) \in I$ , i.e. $K \leq_{m} I$ . As $K$ is undecidable and decidability transfers down $\leq_{m}$ , $I$ is undecidable. Rubric: full credit for the $\emptyset$ -vs-good-function reduction, the index-set invariance step, and the reduction to $\overline{I}$ in the complementary case.

Exercise 7 (hard, symbolic).

Using the recursion theorem (every total computable $f$ has an $n$ with $φ_{n} = φ_{f (n)}$ ), prove there is an index $q$ with $φ_{q} (x) = q$ for all $x$ — a program that, on every input, outputs its own index (a quine).

Hint

Apply s-m-n to the function $(e, x) \mapsto e$ to get a total computable $f$ with $φ_{f (e)} (x) = e$ , then take a fixed point.

Answer

The two-argument function $π (e, x) = e$ is computable; by s-m-n there is a total computable $f$ with $φ_{f (e)} (x) = π (e, x) = e$ for all $x$ — program $f (e)$ ignores its input and prints the constant $e$ . By the recursion theorem $f$ has a fixed point $q$ : $φ_{q} = φ_{f (q)}$ . But $φ_{f (q)} (x) = q$ for all $x$ , so $φ_{q} (x) = q$ for all $x$ . Thus $q$ is a program that outputs its own index on every input. Rubric: full credit for building the constant-printer family by s-m-n and applying the fixed-point theorem to obtain the self-reproducing index.

Advanced results Master

The recursion theorem is the positive form of the diagonal: the same self-application that makes $K$ undecidable, run constructively, gives every effective transformation a fixed point. The theorems below develop the fixed-point machinery, sharpen Rice's theorem to the c.e. case, and map the undecidable problems that lie strictly above $K$ in logical complexity.

Theorem 1 (Kleene recursion / fixed-point theorem). For every total computable $f$ there is an index $n$ with $φ_{n} = φ_{f (n)}$ ^{[Rogers Ch. 11]}. The proof is a single diagonal use of s-m-n: from the partial computable $(v, y) \mapsto φ_{f (s_{1}^{1} (v, v))} (y)$ take an index $w$ and set $n = s_{1}^{1} (w, w)$ , whereupon $φ_{n} (y) ≃ φ_{w}^{(2)} (w, y) ≃ φ_{f (s_{1}^{1} (w, w))} (y) = φ_{f (n)} (y)$ . The fixed point is obtained uniformly in an index for $f$ , and the construction is the mirror image of the halting diagonal — there the self-application produced a contradiction, here it produces an invariant index.

Theorem 2 (second recursion theorem; programs that read their own code). For every partial computable $ψ (e, x)$ there is an index $n$ with $φ_{n} (x) ≃ ψ (n, x)$ for all $x$ ^{[Rogers Ch. 11]}. Thus any program may be written as though it has access to its own index $n$ : define the desired behaviour as $ψ (n, x)$ treating $n$ as a known constant, and the theorem supplies a genuine $n$ realising it. This legitimises definition by effective self-reference — recursive definitions that quote the program being defined, self-modifying schemes, and the formal construction of quines — and re-proves Rice's theorem in one line: if an index set $I$ were decidable, the program "compute $φ_{b}$ if $n \in / I$ , else diverge," self-referential in $n$ , would land on the wrong side of $I$ , contradicting the index-set invariance.

Theorem 3 (Rice-Shapiro). Let $C$ be a class of c.e. sets (partial functions) and $I_{C} = {e : W_{e} \in C}$ its index set. If $I_{C}$ is c.e., then for every c.e. set $A$ : $A \in C$ iff some finite subset $D \subseteq A$ has $D \in C$ ^{[Odifreddi Ch. III]}. Membership in a c.e. index set is therefore determined by finite approximations: a c.e. property of the computed set cannot depend on the whole infinite behaviour, only on finitely much of it. The totality class ${N}$ violates this (no finite set is total), reproving that $Tot$ is not c.e.; the non-emptiness class violates it in the other direction, confirming $\overline{E}$ is c.e. while $E$ is not.

Theorem 4 (undecidable problems beyond halting). Several natural index sets sit strictly above $K$ in the arithmetical hierarchy 42.04.05. The totality problem $Tot = {e : φ_{e} total}$ is $Π_{2}$ -complete; the emptiness problem $Emp = {e : W_{e} = \emptyset}$ is $Π_{1}$ -complete (so $\overline{Emp}$ is $m$ -equivalent to $K$ ); the finiteness problem $Fin = {e : W_{e} finite}$ is $Σ_{2}$ -complete ^{[Soare Ch. 4]}. Outside the index sets lie undecidable problems of different texture: the Post correspondence problem (PCP) — given finite lists of word pairs, is there a matching concatenation? — is undecidable by reduction from $K$ via Turing-machine computation histories; the busy beaver function $Σ (n)$ — the maximum number of $1$ s a halting $n$ -state machine prints — is total but not computable, growing faster than any computable function, since computing it would decide halting for $n$ -state machines; and the word problem for finitely presented groups and Hilbert's tenth problem (Diophantine solvability) are undecidable, the latter because every c.e. set is Diophantine (cross-ref co-produced 42.04.07).

Theorem 5 (the bridge to logic: Church's theorem and the undecidability of arithmetic). Because computation is arithmetisable, $K \leq_{m} Th (N)$ and $K \leq_{m} {┌ σ ┐ : PA ⊢ σ}$ , so the theory of the standard model and the provability set of Peano arithmetic are undecidable ^{[Odifreddi Ch. III]}. Likewise $K$ reduces to first-order validity: from a machine and input one builds a sentence valid iff the machine halts, so the set of valid first-order sentences is undecidable — Church's theorem on the Entscheidungsproblem, cross-ref 42.01.10 pending. The recursion theorem reappears inside logic as the diagonal lemma behind Gödel's first incompleteness theorem 42.01.09 pending: the construction of a sentence asserting its own unprovability is the syntactic twin of the self-referential index of Theorem 2.

Synthesis. The single diagonal at $K$ is the foundational reason the undecidability landscape is connected rather than a list of separate impossibilities: $m$ -completeness makes $K$ a universal source, so every undecidability proof in the chapter is a reduction $K \leq_{m} (\cdot)$ , and this is exactly Rice's theorem read as "reduce $K$ into any extensional class other than the empty and full ones." The recursion theorem is dual to this diagonal — the self-application $φ_{e} (e)$ that defeats the halting checker, run forwards, gives every effective transformation a fixed point, and the second recursion theorem generalises that into programs with access to their own code. Putting these together, Rice-Shapiro stratifies the undecidable index sets by whether the property is captured by finite approximations, which is precisely what lifts $Tot$ , $Fin$ , and $Emp$ off the c.e. floor into $Π_{2}$ , $Σ_{2}$ , and $Π_{1}$ of the arithmetical hierarchy 42.04.05. The bridge from this purely computational diagonal to logic is the arithmetisation that sends $K$ into provability and validity: the central insight is that Gödel's self-referential sentence and Kleene's self-referential program are one construction in two languages, so the incompleteness of arithmetic 42.01.09 pending and the unsolvability of the Entscheidungsproblem 42.01.10 pending are the logical shadow of the halting problem proved here.

Full proof set Master

Proposition 1 ( $K$ is c.e. but not computable). $K = {e : φ_{e} (e) ↓}$ is computably enumerable and not computable.

Proof. $K = dom (ψ)$ for $ψ (e) ≃ U (e, e)$ , partial computable, so $K$ is c.e. If $χ_{K}$ were computable, then $g (e) = φ_{e} (e) + 1$ for $e \in K$ and $g (e) = 0$ for $e \in / K$ is total computable; let $g = φ_{e_{0}}$ . If $e_{0} \in K$ then $g (e_{0}) = φ_{e_{0}} (e_{0}) + 1 = g (e_{0}) + 1$ , impossible; if $e_{0} \in / K$ then $φ_{e_{0}} (e_{0}) ↑$ while $g (e_{0}) = 0$ is defined, contradicting $g = φ_{e_{0}}$ . So $χ_{K}$ is not computable. $□$

Proposition 2 ( $K$ is $m$ -complete). For every c.e. $A$ , $A \leq_{m} K$ .

Proof. Write $A = dom (φ_{a})$ . Let $θ (x, y) ≃ φ_{a} (x)$ , with index $c$ , and $f (x) = s_{1}^{1} (c, x)$ by s-m-n, so $φ_{f (x)} (y) ≃ φ_{a} (x)$ for all $y$ . Then $φ_{f (x)} (f (x)) ↓ ⟺ φ_{a} (x) ↓ ⟺ x \in A$ , whence $x \in A ⟺ f (x) \in K$ . As $f$ is total computable, $A \leq_{m} K$ . $□$

Proposition 3 (recursion theorem). Every total computable $f$ has $n$ with $φ_{n} = φ_{f (n)}$ .

Proof. The function $ψ (v, y) ≃ φ_{f (s_{1}^{1} (v, v))} (y)$ is partial computable, since $s_{1}^{1}$ and $f$ are total computable and $U$ supplies the outer evaluation. Take $w$ with $φ_{w}^{(2)} = ψ$ and set $n = s_{1}^{1} (w, w)$ . For all $y$ , $$ \varphi_n(y) = \varphi_{s^1_1(w,w)}(y) \simeq \varphi^{(2)}w(w, y) = \psi(w, y) \simeq \varphi{f(s^1_1(w,w))}(y) = \varphi_{f(n)}(y), $$ using s-m-n at the first step and the definition of $ψ$ at the last. Hence $φ_{n} = φ_{f (n)}$ . $□$

Proposition 4 (second recursion theorem). For every partial computable $ψ (e, x)$ there is $n$ with $φ_{n} (x) ≃ ψ (n, x)$ for all $x$ .

Proof. By s-m-n there is a total computable $d$ with $φ_{d (e)} (x) ≃ ψ (e, x)$ for all $e, x$ (freeze $e$ as a parameter in $ψ$ ). Apply Proposition 3 to $d$ : there is $n$ with $φ_{n} = φ_{d (n)}$ . Then $φ_{n} (x) ≃ φ_{d (n)} (x) ≃ ψ (n, x)$ for all $x$ . $□$

Proposition 5 (Rice's theorem). If $I$ is an index set with $\emptyset \neq = I \neq = N$ , then $I$ is undecidable.

Proof. Let $e_{\emptyset}$ compute the everywhere-undefined function $\emptyset$ . Without loss of generality $e_{\emptyset} \in / I$ (otherwise apply the argument to the index set $\overline{I}$ , whose undecidability is equivalent). Since $I \neq = \emptyset$ , fix $b \in I$ . Define $θ (x, y) ≃ φ_{b} (y)$ if $φ_{x} (x) ↓$ , and $↑$ otherwise — operationally, run $φ_{x} (x)$ first, then simulate $φ_{b} (y)$ . This is partial computable; let $c$ be an index for it and $f (x) = s_{1}^{1} (c, x)$ . Then $φ_{f (x)} = φ_{b}$ when $x \in K$ and $φ_{f (x)} = \emptyset$ when $x \in / K$ . As $I$ is an index set, $x \in K ⟺ f (x) \in I$ (using $b \in I$ and $e_{\emptyset} \in / I$ ). Thus $K \leq_{m} I$ ; were $I$ computable, $K$ would be, contradicting Proposition 1. $□$

Proposition 6 (Rice-Shapiro, the finite-approximation direction). Let $I_{C} = {e : W_{e} \in C}$ be c.e. If a c.e. set $A \in C$ , then some finite $D \subseteq A$ has $D \in C$ .

Proof. Suppose $A \in C$ but no finite subset of $A$ lies in $C$ . Build, using the recursion theorem, an index $n$ for a c.e. set $W_{n}$ defined by dovetailing: enumerate $A$ , but at each stage also simulate $φ_{n} (n)$ (legitimate since the second recursion theorem hands the construction its own index $n$ ); enumerate elements of $A$ into $W_{n}$ only until the moment, if ever, that $n \in I_{C}$ is witnessed by the c.e. enumeration of $I_{C}$ , then freeze $W_{n}$ at its current finite value. If $n$ is never enumerated into $I_{C}$ , then $W_{n} = A \in C$ , so $n \in I_{C}$ — contradiction, so $n$ is enumerated, at which point $W_{n}$ is a finite subset $D \subseteq A$ with $n \in I_{C}$ , i.e. $D = W_{n} \in C$ , contradicting the assumption that no finite subset of $A$ is in $C$ . Hence some finite $D \subseteq A$ lies in $C$ . $□$

Proposition 7 (the busy beaver function is not computable). Let $Σ (n)$ be the largest number of $1$ s printed by a halting Turing machine with $n$ states (on blank input, fixed alphabet). Then $Σ$ is total but not computable.

Proof. $Σ$ is total because for each $n$ there are finitely many $n$ -state machines and the maximum over the halting ones is a well-defined natural number. Suppose $Σ$ were computable. Then so is any total $B (n) \geq Σ (n)$ , e.g. $B = Σ$ . Given a machine $M$ with $n$ states started on blank tape, run it for a bounded number of steps determined by $B (n)$ together with the finite number of distinct configurations expressible with $B (n)$ tape cells: if $M$ has not halted within that bound it has entered a configuration loop and never halts. This decides whether $n$ -state machines halt on blank tape, and a padding argument reduces the general blank-tape halting problem (hence $K$ after the standard encoding) to it, contradicting Proposition 1. So $Σ$ is not computable, and in fact dominates every computable function eventually. $□$

Connections Master

Models of computation 42.04.01 supplies everything this unit diagonalises against: the enumeration ${φ_{e}}$ , the universal function $U$ that makes $φ_{e} (e)$ a legitimate partial computable object, and the s-m-n theorem that every reduction and the recursion theorem invoke. That unit owns the fixed model and its acceptable-numbering structure; this unit owns the undecidability and fixed-point consequences read off that model — Proposition 4 of 42.04.01 previews the present $K$ result, which is developed here in full with $m$ -completeness.
Computably enumerable sets and the priority method 42.04.03 continue the reducibility theory begun here: $\leq_{m}$ is refined to Turing reducibility $\leq_{T}$ , $K$ becomes the canonical $Σ_{1}$ object, and the existence of c.e. sets strictly between computable and $m$ -complete (Post's problem, solved by Friedberg-Muchnik) is the next structural question. The co-produced unit 42.04.03 builds the c.e. degree structure on top of the $K$ -and-reductions apparatus established here; this unit owns the halting set and the many-one theory it sits atop.
The arithmetical hierarchy 42.04.05 classifies the undecidable problems of Theorem 4 by quantifier complexity: $K$ is $Σ_{1}$ -complete, $Tot$ is $Π_{2}$ -complete, $Fin$ is $Σ_{2}$ -complete, and Rice-Shapiro is the tool that lifts a property off the $Σ_{1}$ floor by showing it is not finitely approximable. That unit relativises $K$ to oracles to build the jump hierarchy; this unit provides the un-relativised base case and the index sets that populate the first levels.
Gödel incompleteness 42.01.09 pending and Church's theorem 42.01.10 pending are the logical projection of the halting diagonal: arithmetisation gives $K \leq_{m} {┌ σ ┐ : PA ⊢ σ}$ and $K \leq_{m} {valid first-order sentences}$ , so undecidability of provability and of validity follow from Proposition 1, and the recursion theorem's self-referential index (Proposition 4) is the computational form of the diagonal lemma that builds the Gödel sentence. The word problem and Hilbert's tenth problem reductions are co-produced in 42.04.07, where the MRDP theorem makes every c.e. set Diophantine.

Historical & philosophical context Master

The halting problem and the recursion theorem are twin consequences of the 1936 analysis of computation. Alan Turing's 1936 paper proved the unsolvability of the Entscheidungsproblem by exhibiting an undecidable problem about his machines — essentially the printing/halting problem — through a diagonal argument modelled on Cantor's proof that the reals are uncountable and on the self-reference in Gödel's 1931 incompleteness theorem ^{[Soare Ch. 2]}. Alonzo Church had reached the undecidability of first-order validity the same year by the $λ$ -calculus route, and the reduction of an undecidable arithmetical problem to validity is now called Church's theorem. Emil Post, in unpublished work of the 1920s–30s and in his 1944 paper on c.e. sets, introduced reducibility and the structure of degrees, posing the problem — whether there is a c.e. set neither computable nor $m$ -complete — that organised the next two decades of the subject.

Stephen Kleene proved the recursion theorem and isolated the s-m-n theorem in the 1930s and systematised them in Introduction to Metamathematics (1952); the fixed-point theorem and its second form gave self-reference a rigorous, paradox-free standing, turning the device that defeats the halting checker into a construction principle. Henry Gordon Rice's 1953 paper established that every extensional property of the c.e. sets — every property of what a program computes rather than how it is written — is undecidable, drawing the boundary the chapter's index-set theory formalises ^{[Rogers Ch. 9]}. John Myhill identified the $m$ -complete c.e. sets with the creative sets and showed them all recursively isomorphic to $K$ , fixing the halting set as the canonical representative of its degree.

Bibliography Master

@article{turing1936computable,
  author  = {Turing, Alan M.},
  title   = {On computable numbers, with an application to the {Entscheidungsproblem}},
  journal = {Proceedings of the London Mathematical Society},
  volume  = {s2-42},
  number  = {1},
  year    = {1937},
  pages   = {230--265}
}

@article{church1936entscheidung,
  author  = {Church, Alonzo},
  title   = {A note on the {Entscheidungsproblem}},
  journal = {The Journal of Symbolic Logic},
  volume  = {1},
  number  = {1},
  year    = {1936},
  pages   = {40--41}
}

@article{rice1953classes,
  author  = {Rice, Henry Gordon},
  title   = {Classes of recursively enumerable sets and their decision problems},
  journal = {Transactions of the American Mathematical Society},
  volume  = {74},
  number  = {2},
  year    = {1953},
  pages   = {358--366}
}

@article{post1944recursively,
  author  = {Post, Emil L.},
  title   = {Recursively enumerable sets of positive integers and their decision problems},
  journal = {Bulletin of the American Mathematical Society},
  volume  = {50},
  number  = {5},
  year    = {1944},
  pages   = {284--316}
}

@article{post1946correspondence,
  author  = {Post, Emil L.},
  title   = {A variant of a recursively unsolvable problem},
  journal = {Bulletin of the American Mathematical Society},
  volume  = {52},
  number  = {4},
  year    = {1946},
  pages   = {264--268}
}

@article{myhill1955creative,
  author  = {Myhill, John},
  title   = {Creative sets},
  journal = {Zeitschrift f\"{u}r mathematische Logik und Grundlagen der Mathematik},
  volume  = {1},
  number  = {2},
  year    = {1955},
  pages   = {97--108}
}

@book{kleene1952metamathematics,
  author    = {Kleene, Stephen C.},
  title     = {Introduction to Metamathematics},
  publisher = {North-Holland},
  year      = {1952}
}

@book{soare2016turing,
  author    = {Soare, Robert I.},
  title     = {Turing Computability: Theory and Applications},
  series    = {Theory and Applications of Computability},
  publisher = {Springer},
  year      = {2016}
}

@book{rogers1967theory,
  author    = {Rogers, Hartley},
  title     = {Theory of Recursive Functions and Effective Computability},
  publisher = {McGraw-Hill},
  year      = {1967}
}

@book{odifreddi1989classical,
  author    = {Odifreddi, Piergiorgio},
  title     = {Classical Recursion Theory, Volume I},
  series    = {Studies in Logic and the Foundations of Mathematics},
  volume    = {125},
  publisher = {North-Holland},
  year      = {1989}
}

Prerequisites

42.04.01

Tier anchors

beginner: Soare 2016 *Turing Computability: Theory and Applications* (Springer) Ch. 2 (read the informal account of the diagonal argument: a single program that asks every program whether it stops on its own code, then does the opposite); Sipser 2013 *Introduction to the Theory of Computation* 3e (Cengage) §4.2 for the halting problem stated and diagonalised before any encoding
intermediate: Soare 2016 *Turing Computability: Theory and Applications* (Springer) Ch. 2-3 (the halting set $K$ and the general halting problem; many-one reducibility $\le_m$ and $m$-completeness; the index sets and Rice's theorem; the recursion / fixed-point theorem from the s-m-n theorem and its applications); Cutland 1980 *Computability: An Introduction to Recursive Function Theory* (Cambridge) Ch. 5-7 (unsolvability, reducibility, Rice's theorem, the recursion theorem)
master: Soare 2016 *Turing Computability: Theory and Applications* (Springer) Ch. 2-4 and the historical notes (the diagonal at $K$, $m$-completeness of $K$, Rice and Rice-Shapiro, the recursion theorem and its iterates, undecidable problems beyond halting); Rogers 1967 *Theory of Recursive Functions and Effective Computability* (McGraw-Hill) Ch. 7-11 (reducibilities, index sets, Rice's theorem, the recursion theorem and the second recursion theorem); Odifreddi 1989 *Classical Recursion Theory, Volume I* (North-Holland) Ch. II-III (the s-m-n / recursion-theorem package, Rice-Shapiro, productive and creative sets, the relation of $K$ to first-order undecidability)

References

Soare, R. I. — Turing Computability: Theory and Applications · Springer, Theory and Applications of Computability (2016). Ch. 2 develops the halting set $K = \{e : \varphi_e(e)\!\downarrow\}$ and the general halting set $K_0 = \{\langle e, x\rangle : \varphi_e(x)\!\downarrow\}$, proves $K$ is computably enumerable but not computable by diagonalising against the enumeration $\{\varphi_e\}$, introduces many-one reducibility $A \le_m B$ (a computable $f$ with $x \in A \iff f(x) \in B$), proves $K$ is $m$-complete among c.e. sets, develops index sets and proves Rice's theorem that any index set other than $\emptyset$ and $\mathbb{N}$ is undecidable, and the Rice-Shapiro theorem characterising the c.e. index sets by their finite approximations; Ch. 2-3 prove the Kleene recursion (fixed-point) theorem from the s-m-n theorem — every total computable $f$ has an $n$ with $\varphi_n = \varphi_{f(n)}$ — with the self-printing-program (quine) and definition-by-self-reference applications, and the second recursion theorem; the totality and emptiness problems $\mathrm{Tot}$, $\mathrm{Emp}$ are shown undecidable (indeed $\Pi_2$- and $\Pi_1$-complete respectively), and the chapter notes connect $K$ to the undecidability of first-order validity (Church) and of arithmetic.
Rogers, H. — Theory of Recursive Functions and Effective Computability · McGraw-Hill (1967). Ch. 7-8: reducibilities, the structure of many-one and one-one degrees, $m$-complete and creative sets, Myhill's theorem that the creative sets are exactly the $m$-complete c.e. sets and are all recursively isomorphic to $K$; Ch. 9: index sets and the proof of Rice's theorem via reduction from $K$, with the productive-set characterisation of the complements of c.e.-incomplete index sets; Ch. 11: the recursion theorem with the standard fixed-point proof from s-m-n, the second recursion theorem $\varphi_{n}(x) \simeq \psi(n, x)$ giving a program access to its own index, the relativised and iterated forms, and applications to defining functions by effective self-reference and to re-deriving Rice's theorem and the undecidability results uniformly.
Odifreddi, P. — Classical Recursion Theory, Volume I · North-Holland, Studies in Logic and the Foundations of Mathematics 125 (1989). Ch. II-III: the s-m-n / recursion-theorem package as the structural core of the subject; the recursion theorem with parameters and the uniformity of fixed points; Rice's theorem and the Rice-Shapiro theorem characterising c.e. index sets as those whose membership is determined by finite sub-functions; productive and creative sets, the equivalence of creativity with $m$-completeness (Myhill); the arithmetisation of computation that turns $K \le_m \{\ulcorner\sigma\urcorner : \mathrm{PA} \vdash \sigma\}$, giving the undecidability of arithmetic, and the reduction of $K$ to first-order validity yielding Church's theorem on the Entscheidungsproblem.

Estimated time

beginner: 20m
intermediate: 50m
master: 90m