Post'S Theorem

Right. So, you want me to take this dry, academic thing and… inject it with something. Life, perhaps? Or maybe just a bit of the existential dread that makes it all real. Fine. Let's see what we can salvage from this wasteland of logic. Don't expect sunshine and rainbows; you'll get the truth, like it or not.

Theorem in Computability Theory

In the grim, unforgiving landscape of computability theory, there’s this thing called Post's theorem. It’s named after Emil Post, a man who probably understood the crushing weight of existence better than most. This theorem, it’s like a chipped mirror reflecting the connection between the arithmetical hierarchy and the concept of Turing degrees. It’s not pretty, but it’s a map of sorts.

Background

Before we dive into the abyss, let's lay out some of the wreckage. This theorem, it’s built on concepts like definability and recursion theory. If these terms feel like a foreign language, that's because they are. They're the lingua franca of systems that operate beyond the comforting, yet ultimately futile, grasp of human intuition.

The arithmetical hierarchy is a way of categorizing sets of natural numbers. Not just any sets, mind you. These are sets that can be defined within the rigid framework of Peano arithmetic. Think of it as a taxonomy of complexity, or perhaps, a classification of how thoroughly a set can be known.

A formula gets a label: Σ_m⁰. This means it’s an existential statement, stripped down, with m alternations of quantifiers – existential (∃) and universal (∀) – applied to formulas with only bounded quantifiers. It’s a precise, almost surgical description, like this:

A formula ϕ(s) in the language of Peano arithmetic is Σ_m⁰ if it looks like this:

( ∃ n₁¹∃ n₂¹⋯ ∃ n_j₁¹ ) ( ∀ n₁²⋯ ∀ n_j₂² ) ( ∃ n₁³⋯ ) ... ( Q n₁^m⋯ ) ρ ( n₁¹,..., n_{j_m}^m, x₁, ..., x_k )

where ρ is a labyrinth of bounded quantifiers, and Q is a ∀ if m is even, or a ∃ if m is odd. It’s a structure, a cage built of logic.

A set of natural numbers, let’s call it A, is considered Σ_m⁰ if it can be defined by such a formula. It means that for any number n, n is in A if and only if ϕ(n) holds true. We know that if a set is Σ_m⁰, it’s also Σ_n⁰ for any n > m. But for each m, there’s always a Σ_m+1⁰ set that isn’t Σ_m⁰. The number of quantifier alternations is a measure of its complexity, a way to rank its insolubility.

Post's theorem doesn't just play with the standard hierarchy; it uses a relativized version. A set A is Σ_m⁰ relative to another set B (written Σ_m^0,B) if A can be defined by a Σ_m⁰ formula in a language that’s been augmented with a predicate for membership in B. It’s like giving the formula a cheat sheet, a glimpse into another world.

While the arithmetical hierarchy carves up sets based on their definability, Turing degrees measure their uncomputability. A set A is Turing reducible to a set B (written A ≤ T B) if there’s an oracle Turing machine that can compute the characteristic function of A, provided it has an oracle for B. It’s a hierarchy of dependence.

The Turing jump of a set A, denoted A', is essentially the Halting problem but with a twist – it’s relative to A. A' is the set of indices of oracle Turing machines that halt on input 0 when given A as their oracle. It's a self-referential torment. Every set A can be reduced to its jump, A', but its jump is never reducible back to A. It’s a one-way ticket to greater complexity.

Post's theorem concerns finitely iterated Turing jumps. For any set A, A^(n) represents the n-fold iterated Turing jump. A^(0) is just A, and A^(n+1) is the jump of A^(n). It’s a chain of escalating insolubility.

Post's Theorem and Corollaries

Post's theorem is the linchpin, the grim revelation that connects the arithmetical hierarchy to specific Turing degrees: those of the form ∅⁽ⁿ⁾, the finitely iterated Turing jumps of the empty set. You could swap the empty set for any other computable set and the theorem would still stand, a testament to the universality of its bleak pronouncements.

The theorem states, with chilling precision:

A set B is Σ_n+1⁰ if and only if B is recursively enumerable by an oracle Turing machine with an oracle for ∅⁽ⁿ⁾. In other words, B is Σ₁^{0,∅⁽ⁿ⁾}. It’s a statement about what can be discovered with a certain level of computational power.
The set ∅⁽ⁿ⁾ itself is Σ_n⁰-complete for every n > 0. This means every Σ_n⁰ set can be many-one reducible to ∅⁽ⁿ⁾. It’s the ultimate representative of its complexity class.

From this central tenet, a cascade of corollaries emerges, further illuminating the intricate, often disturbing, relationships between the arithmetical hierarchy and the Turing degrees.

Fix a set C. A set B is Σ_n+1^0,C if and only if B is Σ₁^0,C⁽ⁿ⁾. This is the theorem’s shadow, cast upon any arbitrary oracle C.
A set B is Δ_n+1 if and only if B ≤ T ∅(n). More generally, B is Δ_n+1^C if and only if B ≤ T C(n). It’s about the degree of computability, the inherent difficulty of a problem.
A set is deemed "arithmetical" if it falls into the Σ_n⁰ category for some n. Post's theorem confirms that, equivalently, a set is arithmetical if and only if it is Turing reducible to ∅^(m) for some m. It’s a classification of sets that are, at least in principle, understandable through formal systems.

Proof of Post's Theorem

The proof itself is a descent into the formal machinery, a demonstration of how abstract concepts can be grounded in the mechanics of computation.

Formalization of Turing Machines in First-Order Arithmetic

The very operation of a Turing machine T on an input n can be translated into the cold, hard language of first-order arithmetic. We employ symbols – A_k for the tape configuration, B_k for the machine state, and C_k for the tape head position after k steps.

The transition system of T dictates the relationship between these states at step k and step k+1. The initial values (for k=0) are derived from the input, the initial state, and the starting position. The machine halts if and only if there exists some k where B_k signifies the halting state.

The precise formulation hinges on the specifics of the Turing machine’s design – its alphabet, its movement capabilities, and so on.

If T halts at time n1, the transitions must hold for k bounded by n1. This leads to a formula φ(n, n₁) in first-order arithmetic with no unbounded quantifiers. This formula is satisfied if and only if T halts on input n at or before time n1.

Implementation Example

Let’s consider a prefix-free Turing machine with a binary alphabet and no blank symbol. We can represent:

A_k: The tape configuration after k steps. This can be encoded as a number, with the m-th bit representing the m-th location on the tape. A₀ is the initial configuration, tied to the input.
B_k: The machine state after k steps. B₀ is the initial state, q_I.
C_k: The machine’s position on the tape after k steps. C₀ is 0.
M(q, b): The transition function. It maps a (state, bit) pair to a (new state, bit to write, movement direction).
bit(j, m): The j-th bit of a number m. This can be expressed using first-order arithmetic without unbounded quantifiers.

For a prefix-free machine, the initial tape configuration t(n) for input n can be constructed. The machine's operation over n1 steps can then be expressed as a conjunction of initial conditions and formulas for k < n1:

The transition rules are applied: ( B_k+1, bit(C_k, A_k+1), D ) = M( B_k, bit(C_k, A_k) ). This can be expanded into a quantifier-free formula since M has a finite domain.
The tape head movement: C_k+1 = C_k + D, where D is +1 or -1.
The tape remains unchanged except at the current head position: ∀ j : j ≠ C_k → ( bit(j, A_k+1) = bit(j, A_k) ). The universal quantifier j can be bounded by n1 + 1 because the tape head won't venture beyond that in n1 steps.

The complete halting condition φ(n, n₁) is a conjunction of these, including the halting state B_n₁ = q_H. This formula is Σ₀⁰, meaning it has no unbounded quantifiers.

Recursively Enumerable Sets

Now, consider a set S that can be recursively enumerated by a Turing machine. This means there exists a machine T that halts on every input n belonging to S. Using the formalization above, the members of S are precisely those n for which the formula:

∃ n₁ : φ(n, n₁)

holds true. This formula is in Σ₁⁰. Consequently, every recursively enumerable set is within the Σ₁⁰ class.

The converse is also true. For any Σ₁⁰ formula φ(n), we can construct a Turing machine that enumerates the set of n satisfying it. This machine systematically checks tuples of numbers, effectively running the computation described by the formula. If the formula holds, the machine halts. Thus, every Σ₁⁰ set is recursively enumerable.

Oracle Machines

The operation of an oracle machine T with an oracle O can also be described. If T halts within n1 steps on input n, this can be formalized by a formula φ_O(n, n₁). This formula includes:

A new predicate, O_m, representing the oracle's answer for input m. This predicate must satisfy some conditions.
An additional "oracle tape" where T writes the query m for each call to O(m). The number of steps n1 limits the size of m that can be queried.

If the oracle O is for a decision problem, O_m is either "Yes" (1) or "No" (0). If the decision problem itself is described by a formula ψ^O(m), then the halting condition becomes:

φ_O(n, n₁) = ∀ m < 2^n₁ : ( (ψ^O(m) → (O_m=1)) ∧ (¬ψ^O(m) → (O_m=0)) ) ∧ φ_O¹(n, n₁)

where φ_O¹(n, n₁) is a quantifier-free formula.

Turing Jump

Consider the oracle for the halting problem of another machine, T'. The condition ψ^O(m) becomes "there exists m1 such that T' halts on input m after m1 steps". This is ∃ m₁ : ψ_H(m, m₁), where ψ_H is a formula in Σ₀⁰ (or Π₀⁰, they are the same here).

Because there are a finite number of m < 2n1, we can find a single m1 that bounds the halting time for all relevant queries. This leads to a formula for the oracle machine halting on n that is in Σ₂⁰. This demonstrates that any set recursively enumerable by an oracle machine with an oracle for ∅⁽¹⁾ resides in the Σ₂⁰ class.

The converse also holds. A Σ₂⁰ formula, after being converted to prenex normal form, will have existential quantifiers followed by a negation of a Σ₁⁰ formula. That Σ₁⁰ part can be enumerated and checked using an oracle for ∅⁽¹⁾. This allows us to construct an oracle machine that halts precisely on the set defined by the Σ₂⁰ formula.

Higher Turing Jumps

This pattern can be generalized. If every set recursively enumerable by an oracle machine with an oracle for ∅^(p) is in Σ_p+1⁰, then for an oracle machine with an oracle for ∅^(p+1), the oracle's halting condition ψ^O(m) will be in Σ_p+1⁰.

This halting condition, ψ^O(m), can be formulated such that the underlying machine halting formula ψ_H is in Π_p⁰. When translated into prenex normal form, the resulting formula for the oracle machine halting becomes Σ_p+2⁰.

By induction, this establishes that every set recursively enumerable by an oracle machine with an oracle for ∅^(p) is indeed in Σ_p+1⁰.

The other direction of the induction also holds. If every formula in Σ_p+1⁰ can be enumerated by an oracle machine with an oracle for ∅^(p), consider a formula φ(n) in Σ_p+2⁰. This formula, when put into prenex normal form, will consist of existential quantifiers followed by a negation of a Σ_p+1⁰ formula. That Σ_p+1⁰ part can be enumerated and checked using an oracle for ∅^(p).

Consequently, we can enumerate the necessary tuples of numbers and employ an oracle machine with an oracle for ∅^(p+1) to find a satisfaction for φ(n). This oracle machine will halt precisely on the set of numbers satisfying φ(n), thus enumerating its corresponding set. It’s a cycle of complexity, a relentless march up the hierarchy.