The diagonal, relativized — and then iterated without end
Give a machine an oracle, and it has a new halting problem it still cannot solve. That single move — from a set to the halting set above it — is the jump, and it never stops climbing: 0 <ₜ 0′ <ₜ 0″ <ₜ …, on through the recursive ordinals. This study follows the operator that is Turing's diagonal made portable. It shows the tower of jumps to be, rung for rung, the arithmetical hierarchy of logic; it answers Post's old question of what lives in the very first gap, with the priority method that founded a field; and it finds, at the end, that the operator generating the whole structure is already written into the order it generates.
the operator · the tower · Post's theorem · Post's problem · finite injury · the shape of the degrees · the diagonal iterated
The reflection ladder of The Ascent climbed by adding, at each rung, the soundness the rung below could not assert. There is an exact twin of that climb in the theory of computation, and it is in some ways more tangible, because its rungs are not theories but oracles, and the thing each oracle supplies is concrete: the answer to the halting problem of the level beneath it. The operator that produces it is the most important single construction in computability theory, and it is the diagonal of The Diagonal in working clothes.
This is a study of the Turing jump and the structure it organizes. We define the operator and prove its one essential property — that it strictly increases degree, for the same diagonal reason Turing's halting problem is undecidable. We climb the tower of iterated jumps into the transfinite, to the edge of the recursive ordinals. We prove Post's theorem, the dictionary that makes the n-th jump and the n-th level of the arithmetical hierarchy the same thing — so that a tower of oracles turns out to be a hierarchy of quantifiers. We take up Post's 1944 question of whether anything lies strictly between the computable sets and the halting problem, watch his own program fail, and watch the finite-injury priority method settle it. We survey the dense and intricate world of the recursively enumerable degrees the method opened. And we close on what ties the jump to everything else in the corpus: it is the diagonal, relativized and iterated, and — by a theorem of Shore and Slaman — definable from nothing but the reducibility order it builds.
Relativize Turing's construction. Hand a machine an oracle for a set A and ask which such machines halt on their own index — that set is the jump of A. It answers every question about A's own halting behaviour, and it is, for the same diagonal reason as the original, strictly beyond A's reach.
First the order the jump lives in. Write A ≤ₜ B — A is Turing reducible to B — when a Turing machine equipped with an oracle for B computes the characteristic function of A: A is decidable given B for free. Mutual reducibility ≡ₜ sorts the sets into Turing degrees, partially ordered by ≤ₜ, with least element 0 — the computable sets — and a join a ∨ b given by A ⊕ B. The degrees measure relative computational power.
The jump of A is the halting problem of machines run with oracle A:
Its one indispensable property is that it always climbs — never sideways, never down, always strictly up.
Read the two halves together. A′ knows more than A — it decides the one thing A provably cannot, its own halting problem — and yet it stands strictly above A, uncomputable from it. The very gain in power is what places it out of reach. This is the diagonal's signature exactly as the corpus draws it elsewhere: the construction that hands a system new strength is the same construction that the system cannot absorb. Here it is a single operator, A ↦ A′, and the whole tower is its iteration.
Apply the jump to its own output and a strictly increasing tower unfolds — the finite jumps 0, 0′, 0″, … and then, taking effective limits, on through the recursive ordinals to the very edge of what computation can name. This tower is the spine of the arithmetical and hyperarithmetic hierarchies.
Start from 0, the computable sets, and iterate. Each jump is strictly above the last, so the finite jumps form a strictly increasing chain 0 <ₜ 0′ <ₜ 0″ <ₜ ⋯ <ₜ 0⁽ⁿ⁾ <ₜ ⋯ — the arithmetical degrees. At the limit, take the effective join of all of them, 0⁽ω⁾ = ⊕ₙ 0⁽ⁿ⁾, and jump again: 0⁽ω⁺¹⁾ = (0⁽ω⁾)′, and onward. Indexed along Kleene's notations for the recursive ordinals, the tower continues to every α below the Church–Kleene ordinal ω₁ᶜᴷ — the least ordinal no machine can name.
Climb it. Each rung is a degree; each tells you what new halting problem it has solved, and — by the theorem of the next section — exactly which level of logical complexity it occupies.
A tower of oracles and a hierarchy of quantifiers were defined for different reasons in different languages — one computational, one logical. Post's theorem says they are the same object. The n-th jump is the Σ⁰ₙ-complete set; climbing the tower by one is adding one quantifier alternation.
Recall the arithmetical hierarchy: Σ⁰₁ the recursively enumerable sets, Σ⁰₂ those defined by a ∃∀ prefix over a computable matrix, and so on up, each level one quantifier alternation beyond the last. Post connected it, level by level, to the jumps of 0.
The dictionary is not abstract — each rung has a natural inhabitant, a decision problem about programs whose complexity is exactly that level and whose Turing degree is exactly that jump:
This is the computational form of a movement the corpus has made before. The Recurrence and The Gap watched a single obstruction migrate upward in complexity — a Π⁰₁ deficit becoming Π¹₁, the arithmetical giving way to the analytical. Post's theorem shows that ascent is a tower of oracles: each quantifier alternation is one application of the jump, each level of definitional complexity a degree of relative computational power. To climb in logical strength and to climb in oracle power are one motion, read in two notations.
Every recursively enumerable set sits at or below the halting problem. Post asked in 1944 whether any of them sits strictly between — an r.e. set undecidable yet not powerful enough to decide halting. He spent a decade trying to build one by making its complement thin, and the attempt instructively failed.
The r.e. sets are the Σ⁰₁ sets, and so by Post's theorem each is recursively enumerable in 0 and therefore ≤ₜ 0′. The two extremes are obvious: the computable r.e. sets have degree 0, and K itself has degree 0′. Post's problem is whether anything r.e. lies strictly in between — whether there is an r.e. set A with 0 <ₜ A <ₜ 0′.
Post's idea was to keep A from coding the halting problem by keeping its complement sparse — too thin to carry that much information. He defined a graded sequence of sparseness conditions: simple (the complement is infinite but contains no infinite r.e. set), then hypersimple, then hyperhypersimple, each stronger than the last. The conditions do lower a set's place under the finer reducibilities — many-one, truth-table. But they do not touch Turing reducibility: there exist simple, even hypersimple, sets that are nonetheless Turing-complete, ≡ₜ 0′. Thinness of the complement is the wrong invariant for ≤ₜ, and Post's problem stood open from 1944 until 1956 — its real content now sharp: is the structure of the r.e. degrees trivial, just {0, 0′}, or is it rich?
Friedberg and Muchnik, independently, answered Post's question — and the answer was richer than a single intermediate degree. There are two recursively enumerable sets neither of which computes the other. The construction that produces them is the finite-injury priority method, the technique on which all of modern degree theory is built.
The result clears the gap completely — not one intermediate degree but a pair of mutually incomparable ones, each therefore strictly between 0 and 0′.
The construction enumerates A and B together, in stages, chasing a list of requirements whose joint satisfaction forces incomparability. Step through what each part of it does.
The finite-injury argument was the first of its kind, and it opened everything after it. Its descendants — the infinite-injury method behind the density theorem, the tree arguments, the 0‴ priority constructions — are the standard machinery of computability theory. What Friedberg and Muchnik showed was not only that the gap is inhabited, but that it can be engineered: r.e. degrees with prescribed relationships can be built to order, requirement by requirement, with conflicts resolved by priority. The diagonal that forbids self-completion, it turns out, leaves behind a structure intricate enough to be designed.
Once the gap was known to be inhabited, the priority method laid the recursively enumerable degrees open as a vast and intricate order — dense, universal for countable structures, stratified by the jump. And then a final turn: the jump, which seemed an operation added from outside, is definable from the bare reducibility order itself.
The single incomparable pair was the doorway. The structure behind it is as rich as an order can be.
This is the kind of closure the corpus prizes. The diagonal generates the jump; the jump generates the order of degrees; and the order, it emerges, already contains a definition of the jump. The construction and the structure it produces are not two things with a one-way arrow between them — the structure remembers its generator. The diagonal's signature is legible not only in the tower it raises but in the bare shape of the order left behind.
The jump is not an isolated tool of computability. It is Turing's diagonal — one of the six limitative results the corpus reads as a single construction — relativized to an oracle and then climbed. Seen so, the tower of degrees is the exact computational twin of the reflection ladder, and Post's theorem is the bridge that identifies the two ascents.
Set the two climbs side by side. In The Ascent, each rung was a theory, and what it added was the soundness — the consistency, the reflected truth — that the theory below could not assert about itself. Here, each rung is an oracle, and what it adds is the halting problem that the degree below could not solve. The motive is identical: a system cannot complete itself, and the missing completion sits exactly one level up.
Each rung adds the soundness the theory below cannot prove of itself. Con(T) is unprovable in T; the climb supplies it from above and never reaches a self-justifying top.
Each rung adds the halting problem the degree below cannot solve. A′ is uncomputable from A; the climb supplies it from above and never reaches a self-deciding top.
And the corpus's invariant stands here in its sharpest single form. Elsewhere it took a sentence, a theory, a cardinal to display the union of power and limit. In the degrees it is one operator. A ↦ A′ both knows more than A and stands strictly above it; the gain in knowledge is the loss of reach, in a single stroke. Between its rungs the priority method finds a structure dense and designable; and the operator itself, by Shore and Slaman, is already written into the order it raises. Power and limit, one construction — relativized, iterated, and legible in the bare shape of what it leaves behind.
A machine handed an oracle is stronger, and still incomplete — and the proof of its incompleteness is the proof that there is somewhere new to climb. That is the whole of the jump, and the whole of the tower it raises: an operator that strictly increases power because, and exactly insofar as, it cannot be absorbed by what it acts on. Climbed through the finite jumps it is the arithmetical hierarchy; climbed through the recursive ordinals it is the hyperarithmetic sets, halting only where computation runs out of names. In the first gap it opens, Post's question becomes the priority method and a field is born; across its whole range the jump is onto, and definable from the order it generates. It is Turing's diagonal made portable, and it carries, into the theory of computation, the one structure this corpus keeps finding everywhere: the construction whose strength is its limit, returning here as a single arrow from a set to the halting problem it cannot reach.