The Jump

Recall what Turing's diagonal actually used, because the whole of this volume turns on how little it was. To prove the halting problem undecidable, Turing supposed a machine H that decides halting, and built from it, by diagonalization, a machine that halts iff it does not — a contradiction. The construction needed two things and only two: that the machines can be effectively enumerated (so there is a list to diagonalize against), and that any machine can be effectively simulated (so the diagonal machine can run H and act against it). It needed nothing about what the machines compute. And that is the opening.

For the same two facts hold of oracle machines. An oracle machine is an ordinary machine equipped with a black box — an oracle — that answers, in one step, membership in some fixed set A: “is n in A?” Such machines can still be enumerated, and still be simulated given the oracle. So Turing's argument runs again, verbatim, with A-oracle machines in place of ordinary ones: there is no A-oracle machine that decides whether an arbitrary A-oracle machine halts. Relative to A, there is a halting problem, and it is undecidable relative to A. The diagonal never depended on the starting point; relativize the starting point, and the diagonal relativizes with it.

This relativized halting problem is the jump of A, written A′ — precisely, the set of indices of A-oracle machines that halt on input 0 when given the oracle A. Two facts make it the engine of all that follows, and both are the diagonal, read the two ways the collection knows. First, A′ is at least as hard as A: with an oracle for A′ one can decide A, so A ≤ₜ A′ — the positive reading, A′ computes A. Second, and crucially, A′ is strictly harder: there is no way to decide A′ from A alone — this is the relativized diagonal, the contrapositive reading, the wall. So the jump strictly increases difficulty: A <ₜ A′, always, for every set A. The diagonal, packaged as an operator, takes any problem and returns one strictly harder. Apply it to the empty set — to the decidable problems, which need no oracle — and A′ is the ordinary halting problem, written 0′. The halting problem is the jump of the trivial; and the jump does not stop there.

So iterate. Begin at the bottom: degree 0, the decidable problems, solvable with no oracle at all. Jump once and you reach 0′, the halting problem — the first rung above the decidable, strictly harder than 0. But 0′ is now just another set, and the jump applies to it: 0″, the jump of the jump, is the halting problem for machines equipped with a halting oracle — strictly harder than 0′, by the same relativized diagonal. And 0‴, harder still; an infinite ascending sequence 0 < 0′ < 0″ < 0‴ < ⋯, each rung the jump of the one below, each strictly above it, every step the identical construction applied at a new height.

And the finite rungs are not the top. Collect all the finite jumps 0⁽ₙ⁾ at once — take their effective join, the single set coding the whole sequence — and call it 0⁽ω⁾. It sits above every finite rung; and it is a set like any other, so the jump applies to it: 0⁽ω⁺¹⁾, and onward. The iteration climbs through the transfinite, with a jump for every ordinal that can be effectively described — every computable ordinal — and, by a theorem of Spector, the result depends only on the ordinal, not on the description used to reach it. The tower of the unsolvable is not merely infinite; it is transfinite, indexed by the computable ordinals, climbing as high as the collection's other volumes climbed in the proof-theoretic ordinals — and by the same kind of ladder.

Pause on the reconception this forces. The naive picture of computability is binary: a problem is decidable, or it is not. The jump shatters the binary. Above “decidable” rises not a single undivided realm of “the undecidable” but an endless, strictly ordered staircase — degree after degree, each properly harder than all below it, no top floor. To be undecidable is not to occupy a single condition; it is to stand somewhere on an infinite ascent, and the question “how undecidable?” has infinitely many answers. The halting problem, which the collection met as the undecidable problem, is merely the first rung — and the diagonal that built it is a staircase-builder, climbing forever, one jump per storey.

The tower has a logical twin, and the identity of the two is among the most beautiful facts in the subject. Forget oracles for a moment and classify arithmetical statements by their quantifier complexity. A statement is Σ⁰₁ if it has the form “there exists n such that R(n)” with R decidable — one existential quantifier over a computable matrix. It is Π⁰₁ if it reads “for all n, R(n)” — one universal. Σ⁰₂ allows “there exists… for all…”, two alternations beginning with ∃; Π⁰₂ allows “for all… there exists…”, two beginning with ∀; and so up the arithmetical hierarchy, the subscript counting quantifier alternations, the letter recording whether the outermost quantifier is existential (Σ) or universal (Π). This is a purely syntactic measure — how complex a sentence must be to express a property — with nothing of oracles or machines in it.

And yet it is the tower exactly. Post's theorem, after Emil Post, ties the two hierarchies rung for rung. A set is Σ⁰₁ precisely when it is computably enumerable — listable — and the hardest such set, the universal one, is the halting problem 0′. More generally: the n-th jump 0⁽ₙ⁾ is Σ⁰ₙ-complete, the hardest set at level n, for every n ≥ 1; a set is Σ⁰ₙ₊₁ exactly when it is computably enumerable relative to 0⁽ₙ⁾; and a set is computable from the n-th jump exactly when it is Δ⁰ₙ₊₁, lying in both Σ and Π at level n+1. The syntactic complexity of a property — its quantifier alternations — equals the computational height of the oracle one would need to decide it — its jumps.

Read off what this means in concrete cases, for it makes the correspondence vivid. The halting problem — “does machine e halt?” — is “there exists a halting computation,” one existential, Σ⁰₁, and it sits at the first jump 0′. Totality — “does machine e halt on every input?” — is “for all inputs, there exists a halting time,” a ∀∃ alternation, Π⁰₂, and it sits at the second jump 0″: to decide whether a program is total, a halting oracle is not enough — you need the jump of the halting oracle. Cofiniteness climbs to Σ⁰₃ and the third jump. Each quantifier alternation you must prepend to express a property is one more jump up the tower you must climb to decide it. The ladder of logical complexity and the ladder of computational hardness are not analogous structures; they are one structure, climbed in two notations, and Post's theorem is the statement that they coincide.

A sharper question now, the one that opened the modern theory of degrees. The tower's first two rungs are 0, the decidable, and 0′, the halting problem. Between them — is there anything? Are there problems strictly harder than decidable yet strictly easier than halting, intermediate degrees of unsolvability? The question is most pointed for the computably enumerable sets — the listable ones, the natural family to which the halting problem itself belongs. Every c.e. set is at most as hard as 0′. Post asked, in 1944: is every c.e. set either decidable (degree 0) or as hard as the halting problem (degree 0′)? Or is there a c.e. set of strictly intermediate degree — undecidable, but too weak to solve halting?

The crude diagonal cannot answer, and the reason is instructive. Diagonalization, the collection's master tool, naturally produces sets that are hard — to diagonalize against all decision procedures is to land at or above the halting problem. Post himself, in 1944, tried to build an intermediate set by controlling its complexity directly — making it “thin” in various precise senses, so that it could not be too hard — but every attempt either left the set decidable or let it climb all the way to 0′. The diagonal is a blunt instrument: it builds a wall, but not a wall of a prescribed, intermediate height. Post's problem stood open for thirteen years precisely because the one construction everyone knew — diagonalization — was too crude to hit a target strictly between the two known rungs.

The answer, found independently by Friedberg in the United States and Muchnik in the Soviet Union, both in 1957, is yes — and emphatically so. There exist c.e. sets of intermediate degree: undecidable, yet strictly below the halting problem. In fact there are infinitely many, and — the sharper result the same method delivers — there are incomparable ones: c.e. degrees a and b, each strictly between 0 and 0′, neither computable from the other. The first level of the tower is not a single step but a whole intricate landscape. Between the decidable and the halting problem lies not a gap but a richly structured interior of mutually-incomparable difficulties — and the structure goes on, for the c.e. degrees alone form a complicated, dense partial order whose full description is still, decades later, an active subject. The unsolvable is not just a staircase; even a single step of it, looked at closely, opens into a world.

How Friedberg and Muchnik built their intermediate sets is the deepest part of the story, and it is the diagonal grown subtle — transformed from a single decisive stroke into a patient, staged, self-correcting process. To see the difficulty, count what such a construction must achieve. To build a c.e. set A that is undecidable, one must defeat every possible decision procedure: for each machine Mₑ, a requirement Nₑ saying “Mₑ does not decide A.” To keep A strictly below the halting problem, one must defeat every possible reduction of 0′ to A: for each machine, a requirement Pₑ saying “this machine, with oracle A, does not compute the halting problem.” There are infinitely many requirements of each kind, and — here is the knot — they conflict. Acting to satisfy one, by putting a number into A or keeping it out, can undo the work already done for another.

The priority method resolves the conflict by the device its name records. List all the requirements — the Nₑ and the Pₑ together — in a single priority ordering, a queue: requirement 0 highest, then 1, and so on. At each stage of the construction, let each requirement act when it sees a chance to make itself true — typically by enumerating some number into A. When two requirements clash, the one of higher priority wins, and its action may injure a lower-priority requirement, spoiling what that requirement had arranged. The injured requirement is not abandoned; it simply starts over, looking for a fresh opportunity. The construction proceeds stage by stage — requirements acting, injuring, recovering — and the set A is built as the union of everything enumerated.

And the argument that it works is the heart of the technique, a finite-injury argument of real elegance. One proves, by induction on the priority ordering, that each requirement is injured only finitely often. The highest-priority requirement is never injured — nothing outranks it — so it acts once and stays satisfied. The second can be injured only by the first, hence at most finitely often, so once the first settles, the second settles too. In general, requirement n can be injured only by the finitely many requirements above it, each of which eventually stops acting; so after some stage, requirement n is never injured again, and from then on remains permanently satisfied. Every requirement is met in the end — A is undecidable, as all the Nₑ hold, and strictly below 0′, as all the Pₑ hold: an intermediate degree, built. Where the halting problem's diagonal was one stroke, acting once and for all, the intermediate degrees demand a diagonalization spread across infinitely many stages, conflicts ordered by priority and damage bounded by finiteness — the collection's construction, refined into a technique of remarkable delicacy, and the seed of the entire modern theory of degrees.

Step back to the collection's frame, and weigh what the jump has shown. Elsewhere the diagonal appeared as an event — one construction, one limit: this sentence is unprovable, this problem undecidable, this set uncountable. The jump reveals it as something larger: a generator. Applied once, it gives a limit. Relativized, it gives a strictly harder limit. Iterated, an endless tower; iterated transfinitely, a tower indexed by all the computable ordinals. And between its rungs — even between the first two — lies a structured interior of incomparable degrees, requiring its own refinement of the construction to reach. The single move the collection began with does not produce the famous limits one at a time, in isolation; it produces, by its own relativization and iteration, an unbounded, intricately ordered universe of them.

That universe — the Turing degrees — deserves a word, for it is the diagonal's true monument. It is not a line: the degrees are partially ordered, with incomparable elements everywhere, the c.e. ones already dense and tangled. It is uncountable. It is locally complicated in ways that took the priority method and its many elaborations — infinite-injury arguments, and finer still — decades to begin to chart, and it is not charted yet; the structure of the degrees has been a central object of mathematical logic for seventy years and remains an active frontier. The crude question the collection started from — “what can be computed?” — has as its true answer not a line from “yes” to “no” but this vast, irregular, still-unmapped landscape, every point of it a degree of unsolvability, every degree generated by the diagonal applied at some height.

And so the collection's lesson reaches its sharpest form. The diagonal is not the architect of a wall; it is the architect of an endless landscape of walls, each the same construction raised one storey higher, the whole of it generated by relativizing and iterating a single move. The first incompleteness theorem, the halting problem, Cantor's uncountability — these were never isolated cliffs. They were the first visible storeys of a structure that climbs without end and ramifies without bound, and the construction that built the first storey is the construction that builds them all. The ascent volume climbed the proof-theoretic ladder, theories rising in logical strength; this volume climbs the computational one, problems rising in hardness; the arithmetical hierarchy is where the two ascents meet, and the diagonal is the engine of both. The collection set out to find the one construction behind the famous limits. The jump shows that the same construction, left to its own relativization, generates a whole cosmos of limitation — and that the boundary of the knowable, which looked from a distance like a single wall, is on closer view an endless, structured, still-uncharted ascent, every storey of it the diagonal, one height higher.