The Arithmetical Hierarchy and the Turing Jump

Saying a problem is undecidable is a single bit of information. Many problems are undecidable, and they are not equally hard: some are recognizable, some are co-recognizable, some are neither, and some can decide the halting problem itself. The arithmetical hierarchy assigns each set a level based on how many alternating quantifiers over a decidable predicate it needs, and the Turing jump is the operation that walks up that ladder one rung at a time.

Quantifier prefixes as a classification

A set A ⊆ ℕ is Σ₁ when it can be written as {n : ∃y. R(n, y)} with R decidable. That is exactly the definition of a recognizable set: the machine that recognizes A searches for y, and halts when it finds one. A set is Π₁ when it is {n : ∀y. R(n, y)}, which is the complement of a Σ₁ set, hence co-recognizable.

Continue upward. A set is Σ₂ when it is {n : ∃y ∀z. R(n, y, z)}, Π₂ when {n : ∀y ∃z. R(n, y, z)}, and in general Σ_k allows k alternating quantifier blocks beginning with ∃, Π_k the same beginning with ∀. A set that is both Σ_k and Π_k is Δ_k. Every decidable set is Δ₁, and Δ₁ = Σ₁ ∩ Π₁, which is the complement criterion from Recognizers, Dovetailing, and Complement Asymmetry restated in quantifier form.

Two structural facts hold immediately. First, the levels are nested in one direction only: Σ_k ⊆ Σ_{k+1}, because a leading ∃ over a dummy variable can always be added, and similarly for Π. Second, the complement of a Σ_k set is Π_k and vice versa, so the hierarchy is symmetric about each Δ level. From the two, Σ_k ⊆ Δ_{k+1}: padding a Σ_k formula with a dummy quantifier block yields both a Σ_{k+1} and a Π_{k+1} description of the same set.

The strictness of these inclusions is not obvious and is not proved by counting. It follows from the jump theorem below, which produces, for each k, a set that is Σ_k and not Π_k. Without such a witness, the hierarchy could collapse at some finite level, and the quantifier-counting description would be a classification of syntax rather than of difficulty.

The halting set as the first rung

The halting problem sits at Σ₁ and not at Π₁. It is Σ₁ because “M halts on w” is ∃t. “M has halted by step t”, and the predicate after the quantifier is decidable by bounded simulation. It is not Π₁ because its complement is not recognizable: if both K = {⟨M, w⟩ : M halts on w} and its complement were Σ₁, both would be recognizable, and the complement criterion would give a decider, contradicting the result in Mapping Reductions and the Halting Problem.

Sets that are Σ₁-complete — Σ₁ and able to decide every Σ₁ set by a many-one reduction — include the halting set, the acceptance set, and the set of machines that accept at least one string. They are all the same problem in disguise, which is why the standard reductions form a dense web: the undecidability results of the previous articles are all statements about one rung of the ladder.

The same reasoning applies one level up. Totality, the set {⟨M⟩ : M halts on every input}, is Π₂: ∀w ∃t. “M halts on w by step t”. Its complement is Σ₂ and not Σ₁. So “does this machine halt everywhere” and “does it halt here” are not merely different in difficulty: a machine deciding totality would decide the halting problem with one query, since M halts on a given w exactly when a machine constructed to halt only if M fails on w does not halt everywhere. The converse fails, because a halting-set oracle answers only single-input questions and does not by itself settle an unbounded universal quantifier over inputs.

The jump operator

For a set A, the jump A′ is the halting problem relativised to A: A′ = {⟨e⟩ : the e-th machine with oracle A halts on input e}. The definition is a diagonal one, exactly as in the unrelativised case, and the diagonal argument relativises without change: no machine with oracle A decides A′, because the diagonal machine built from a supposed decider would be a machine with oracle A and would contradict itself on its own index.

The jump has three properties that make it the right ladder operator.

First, A′ is strictly harder than A: A ≤_T A′ but A′ ≰_T A. The first inequality holds because a machine with oracle A′ can decide A by asking whether a machine that ignores its oracle and halts exactly on inputs in A halts on a given input. The second is the relativised diagonal.

Second, the jump commutes with the hierarchy levels. Post’s theorem states that a set B is Σ_{k+1} in the unrelativised hierarchy if and only if B is Σ₁ relative to ∅^(k), where ∅^(k) is the k-th jump of the empty set. The same theorem in the form used for classification says that B is Δ_{k+1} exactly when B ≤T ∅^(k). So the k-th jump decides precisely the Δ{k+1} sets, and the ladder of jumps is the ladder of quantifier levels.

Third, the jump is monotone with respect to Turing reducibility: A ≤_T B implies A′ ≤_T B′. This makes the operator well defined on degrees, and it is what allows the structure of degrees to be studied as an ordered set with a successor operation.

Iterating gives ∅′ (the halting problem), ∅″ (which decides totality and every other Δ₂ question), ∅‴, and so on. Each step is a strictly harder problem: ∅′ decides whether a machine halts on a given input, and ∅″ decides the Π₂ questions that quantify over all inputs, one more alternating prefix per jump.

Why the hierarchy does not collapse

Take B_k = {e : the e-th machine with oracle ∅^(k) halts on input e}. Relativising the first-rung argument, B_k is Σ₁ relative to ∅^(k), so by Post’s theorem it is Σ_{k+1} in the absolute hierarchy. It is not Π_{k+1}: if it were, B_k would be Δ_{k+1}, hence decidable by an oracle machine for ∅^(k), and the relativised diagonal argument says no such machine decides B_k. So B_k is Σ_{k+1} and not Π_{k+1}, which separates the two levels.

The construction is uniform in k, so it gives a distinct witness at every finite level. No finite level absorbs the next, and the union of all levels is a proper subclass of all sets: there are sets that are not arithmetical at all, meaning not definable by any finite quantifier prefix over a decidable predicate.

A concrete example of such a set is the set of true sentences of first-order arithmetic. Truth in the standard model of arithmetic is not definable by any formula of the language, by Tarski’s undefinability theorem, so it cannot be one of the arithmetical sets, all of which are definable by some formula. That gives a set beyond every finite rung. The jump can be iterated into the transfinite to keep climbing, a construction that requires ordinal notations and leads to hyperarithmetic theory.

The limit lemma and approximations

One of the most useful facts about the first jump is Shoenfield’s limit lemma: A ≤_T ∅′ if and only if there is a computable function g(n, s) such that for every n, the sequence s ↦ g(n, s) is eventually constant with limit equal to A’s characteristic function at n. In words, a set is decidable relative to the halting problem exactly when it can be approximated by a computable sequence that converges on each argument, with no computable bound on when convergence occurs.

The lemma explains why ∅′ appears so often in practice. Any question answerable by a procedure that revises its guess finitely often — a search that may restart, a learning process that may change its mind — is decidable relative to ∅′ at level Δ₂, with the mind changes playing the role of the stages s. It also gives a clean way to read the hierarchy as a ladder of approximations: Δ₂ is exactly the class of limit-computable sets, and deciding whether an approximation has converged requires an oracle one jump higher, so each further quantifier alternation buys one more layer of “approximating the approximation”.

def limit_decides(approx, n, max_stage):
    """Decide A(n) from a converging approximation g(n, s) -> {0, 1}.
    Returning None is the honest answer: convergence is not detectable
    without an oracle for the halting problem."""
    prev = approx(n, 0)
    settled_at = 0
    for s in range(1, max_stage):
        cur = approx(n, s)
        if cur != prev:
            prev, settled_at = cur, s      # the approximation changed its mind
    # Without an oracle, a long stable run is only evidence, never proof.
    return prev if settled_at < max_stage - 8 else None

A machine with an oracle for ∅′ can wait a bounded number of stages and ask whether the approximation changes again within the next stage of that bound; if it does not, the value it is holding is the limit. The bound is a number the machine computes from its input, not something it can discover by running the approximation. The code above has no such bound available, so it can only report a value it has seen, flagged as unproven — which is exactly the gap the lemma measures.

Reduction notions and what they measure

The hierarchy is usually stated with many-one reducibility, but the jump is naturally a Turing-reducibility operator. The two notions diverge in ways that matter for classification.

Many-one reductions preserve the Σ_k level in both directions and are the right tool for completeness results: a Σ_k-complete set is one that every Σ_k set reduces to, and the halting set is Σ₁-complete under ≤_m. Turing reductions are more permissive: a Turing reduction from A to B requires only that A be decidable given B as an oracle, so it can ask many questions and combine the answers non-monotonically.

The distinction has a practical analogue. A reduction that transforms one instance into one instance preserves the structure of the problem; a reduction that solves a problem by querying an oracle for another preserves only the computability. When a claim describes problem B as “as hard as” problem A, the reduction notion determines whether the claim is about instance-level encoding or about oracle access, and the two are not interchangeable. In the resource-bounded setting the same distinction separates many-one completeness from Turing completeness, and for some classes the second is strictly broader than the first.

Where the ladder is used

Three applications justify the machinery.

Classifying verification questions. Whether a program halts, whether it halts on all inputs, whether it halts on all inputs where a second program halts, and whether a specification is satisfied by every execution are questions at different levels. Naming the level fixes what an oracle would have to supply, and therefore what a sound incomplete tool can and cannot be expected to prove. A tool that always terminates and never gives a wrong answer is deciding a Δ level; a tool that is complete for a Σ level must be allowed to loop on no-instances.

Proving that a problem is not merely undecidable but highly so. A reduction from a Σ₂-complete problem rules out not only decidability but also decidability relative to the halting oracle. That is a much stronger statement, and it is what distinguishes questions like “does this rewriting system terminate on all terms” from “does it terminate on this term”.

Calibrating oracle-based algorithms. An algorithm that queries a SAT oracle polynomially many times sits at a specific level of the relativised polynomial hierarchy. The arithmetical hierarchy is the unbounded-resource shadow of that structure, and the same diagonal techniques establish the separations in both settings. The finite-resource version is a different subject with its own open problems; the infinite-resource version is completely settled, which is why it is the right place to learn the technique.