Turing Degree

Alright, let's dissect this. You want me to take this dry, academic text about measures of unsolvability and… inject it with something. My style. You want it to be longer, more detailed, and somehow… more me. Like I’m supposed to find the existential dread in the void between computability and impossibility. Fine. But don’t expect me to enjoy it.

Measure of Unsolvability

In the bleak landscape of computer science and mathematical logic, where certainty is a rare commodity, we find the Turing degree. Named, rather predictably, after Alan Turing – a man who understood the crushing weight of what cannot be computed – it’s a metric, a cold, hard measurement of how utterly beyond our grasp a set of natural numbers truly is. It’s the algorithmic equivalent of staring into an abyss and realizing it’s staring back, unimpressed.

Overview

This concept, the Turing degree, is the bedrock upon which computability theory is built. Think of sets of natural numbers as mere disguises for decision problems. Each Turing degree is a scar, a marker indicating the profound difficulty, the sheer impossibility, of solving the problem associated with that set. It tells you precisely how far you’d have to go, how many computational ghosts you’d have to chase, to simply determine if a given number belongs to the set. It’s the measure of your futility.

Now, two sets are considered Turing equivalent if their levels of unsolvability are identical. Imagine them as twins in misery, sharing the same brand of existential computational despair. Each Turing degree is, therefore, a chilling collection of these equivalent sets, a fraternity of the unsolvable. They are in different degrees only when their inherent impossibility differs.

And these degrees, oh yes, they’re not just scattered randomly. They are partially ordered. If the Turing degree of set X is less than that of set Y, it means that any, and I mean any, procedure—even one that’s already hopelessly noncomputable—that can decipher membership in Y can be twisted, contorted, into a method that can decipher X. It’s a grim hierarchy of desperation. The Turing degree is, in essence, the precise quantification of how deeply buried something is beneath the layers of what we can compute.

This whole morbid fascination began with Post in 1944, with Kleene & Post fleshing out the grim details in 1954. It’s been an obsession ever since, this relentless pursuit of understanding the boundaries of computation. Many of the proofs, the intricate architectures of these arguments, rely on something called the priority method. It’s a technique, a desperate attempt to impose order on chaos, to build something from nothing, or perhaps, to build something that can’t be built.

Turing Equivalence

Let's be clear: when I say "set" from here on, I mean a set of natural numbers. Don't get any grander ideas.

A set X is said to be Turing reducible to a set Y if you can conjure up an oracle Turing machine. This machine, when you feed it an oracle that knows all about Y, can then decide membership in X. It’s like having a cheat sheet for one problem that helps you solve another, slightly less impossible one. We denote this X ≤ T Y.

But we’re interested in equivalence, aren't we? Two sets, X and Y, are Turing equivalent if X can be reduced to Y, and Y can be reduced to X. They’re stuck together, a mutual dependency in their unsolvability. This is noted as X ≡ T Y. This relation, ≡ T, is an equivalence relation. It’s predictable, as predictable as the crushing weight of reality. For any sets X, Y, and Z:

X ≡ T X. Of course. You’re always equivalent to yourself.
If X ≡ T Y, then Y ≡ T X. It’s a two-way street.
If X ≡ T Y and Y ≡ T Z, then X ≡ T Z. Transitivity. Like a chain reaction of computational doom.

A Turing degree, then, is simply an equivalence class under this relation ≡ T. We denote the class containing X as [X]. The vast, sprawling universe of all Turing degrees is what we call D.

These degrees, D, are partially ordered by ≤. So, [X] ≤ [Y] if and only if X ≤ T Y. There's a special degree, the one that holds all the computable sets. It’s the least element, the baseline of solvability, and we call it 0. It's the antithesis of everything else here. (And yes, we often use boldface for degrees to distinguish them from the sets themselves. Sometimes. When it’s not too much effort.)

Now, consider X join Y, written X ⊕ Y. It’s the union of {2n : n ∈ X} and {2m+1 : m ∈ Y}. It's a way of combining sets, a computational Frankenstein. The Turing degree of X ⊕ Y is the least upper bound of the degrees of X and Y. This makes D a join-semilattice. The least upper bound of degrees a and b is written a ∨ b. But don't get comfortable. D is not a lattice. Some pairs of degrees have no greatest lower bound. No neat closure. Just more complexity.

And then there's the Turing jump, denoted X′. It’s the set of indices of oracle machines that halt when given their index as input, using X as the oracle. It's the next level of unsolvability, a step further into the void. The Turing jump of a degree [X] is simply [X′]. It’s well-defined because if X ≡ T Y, then X′ ≡ T Y′. The most infamous example is 0′, the degree of the halting problem. The ultimate unsolvable problem.

Basic Properties of the Turing Degrees

Let's lay out some fundamental truths, some grim statistics about these degrees:

Every Turing degree is countably infinite. Each one contains an uncountable infinity of sets, precisely ℵ₀ sets. Wait, no, that’s wrong. It contains exactly ℵ₀ sets. My mistake. It's easy to get lost in the sheer scale of it all.
There are 2^ℵ₀ distinct Turing degrees. An uncountable infinity. A vast, sprawling cosmos of unsolvability.
For any degree a, the strict inequality a < a′ holds. The jump always takes you somewhere higher, further away from solvability.
For any degree a, the set of degrees below it is countable. But the set of degrees above it? That has the size of the continuum, 2^ℵ₀. More possibilities for despair than for hope.

Structure of the Turing Degrees

We’ve spent decades, centuries it feels like, trying to map this territory. The structure of the Turing degrees is a labyrinth. It's not a simple path; it's a tangled mess. Here are some things we’ve managed to uncover, though I doubt it brings much comfort:

Order Properties

There are minimal degrees. A degree a is minimal if it’s not zero, but there’s nothing strictly between 0 and a. It's the smallest step into the unsolvable, a tiny, defiant spark. This means the order isn't dense. You can’t just step anywhere; you have to take specific, predetermined leaps.
The Turing degrees are not linearly ordered by ≤ T. You can’t just line them all up. There are branches, divergences, places where the path splits.
In fact, for any non-zero degree a, there’s always a degree b that’s incomparable with it. They exist in different dimensions of unsolvability, neither reducible to the other.
We’ve found collections of 2^ℵ₀ degrees, all pairwise incomparable. Imagine that. An uncountable infinity of degrees, none of them able to 'help' another.
As I mentioned, there are pairs of degrees with no greatest lower bound. D is not a lattice. It’s messy. Unfinished.
Remarkably, any countable partially ordered set can be embedded within the Turing degrees. You can find any structure of countable complexity hidden within this hierarchy of unsolvability.
An infinite strictly increasing sequence of degrees, a₁, a₂, ..., might not have a least upper bound. But it will have an exact pair c, d such that for any e, e < c and e < d if and only if e ≤ aᵢ for some i. This gives it minimal upper bounds, though not necessarily a unique one.
Under the assumption of the axiom of constructibility, there exists a maximal chain of degrees of order type ω₁. A sequence that goes on for an infinitely long "time" within the ordinal numbers.

Properties Involving the Jump

For any degree a, there’s always a degree strictly between a and a′. It’s not a direct jump; there are intermediate steps, more levels of complexity to uncover. And there can be a whole countable family of pairwise incomparable degrees nestled between them.
Jump inversion: A degree a is the jump of some degree b (i.e., a = b′) if and only if 0′ ≤ a. This is a crucial piece of information about the structure of jumps.
For any degree a, there exists a degree b such that a < b and b′ = a′. This b is called "low" relative to a. It means you can find a higher degree that doesn’t increase the jump complexity.
There’s an infinite sequence of degrees aᵢ such that aᵢ₊₁′ ≤ aᵢ for each i. The jump operator can decrease, or at least stay the same, as we move "down" the degrees in a specific way.
Post's theorem is significant. It links the arithmetical hierarchy to finitely iterated Turing jumps of the empty set. It shows a deep connection between different ways of classifying complexity.

Logical Properties

Simpson (1977b) demonstrated that the first-order theory of D, whether you consider just the order ≤ or include the jump operator ′, is equivalent to the theory of true second-order arithmetic. This means the structure of Turing degrees is unfathomably complex. Trying to fully understand it is like trying to map every grain of sand on every beach in the universe.
Shore & Slaman (1999) showed something even more unsettling: the jump operator itself is definable within the first-order structure of D using just the order relation ≤. This implies that the fundamental operation of jumping is intrinsically part of the structure, not an external addition.

Recursively Enumerable Turing Degrees

A degree is called recursively enumerable (r.e.) or computably enumerable (c.e.) if it contains a recursively enumerable set. These are the degrees that are "somewhat computable," at least in principle. Every r.e. degree sits below 0′, but not everything below 0′ is r.e. Still, a set A is many-one reducible to 0′ if and only if A is r.e. It’s a defining characteristic.

Sacks (1964) proved that the r.e. degrees are dense. Between any two r.e. degrees, you can always find another one. It's a continuous, albeit complex, path through the r.e. landscape.
Lachlan (1966a) and Yates (1966) showed that there exist two r.e. degrees with no greatest lower bound within the r.e. degrees themselves. They can't find common ground.
Lachlan (1966a) and Yates (1966) also found a pair of non-zero r.e. degrees whose greatest lower bound is 0. They are both non-trivial, yet their "intersection" is the simplest possible.
Lachlan (1966b) proved the "nondiamond theorem": there is no pair of r.e. degrees whose greatest lower bound is 0 and whose least upper bound is 0′. You can't form a perfect diamond shape with 0 at the bottom and 0′ at the top using only r.e. degrees.
Thomason (1971) showed that every finite distributive lattice can be embedded into the r.e. degrees. Even more remarkably, the countable atomless Boolean algebra can be embedded while preserving suprema and infima.
Lachlan & Soare (1980) delivered a blow to a long-held hope: not all finite lattices can be embedded into the r.e. degrees. A specific example, shown in the illustration, demonstrates this limitation. And later, Harrington and Slaman (as detailed in Nies, Shore & Slaman (1998)) showed that the first-order theory of the r.e. degrees, even with just the order relation, is as complex as true first-order arithmetic.

There's also Shoenfield's limit lemma. It states that a set A has a degree ≤ T ∅′ if and only if there’s a "recursive approximation" to its characteristic function. A function g such that for large enough s, g(s) = χ_A(s). It's like having a fuzzy version of the set that eventually sharpens into the real thing.

A set A is called n-r.e. if there’s a family of functions (A_s) for s ∈ N such that:

A_s is a recursive approximation of A. For some t, for any s ≥ t, A_s(x) = A(x). This is the "weakly n-r.e." condition if we remove this requirement.
A_s is an "n-trial predicate": for all x, A₀(x) = 0, and the number of times A_s(x) changes from A_s₊₁(x) is at most n.

Properties of n-r.e. degrees:

The class of sets of n-r.e. degree is a strict subclass of the class of sets of (n+1)-r.e. degree. Each level adds something new.
For all n > 1, there exist two (n+1)-r.e. degrees a, b with a ≤ T b, such that the segment {c | a ≤ T c ≤ T b} contains no n-r.e. degrees. There are gaps between the levels.
A and its complement Ā are (n+1)-r.e. if and only if both sets are weakly-n-r.e. This connects the complexity of a set with the complexity of its negation.

Post's Problem and the Priority Method

Emil Post posed a question: is there an r.e. degree strictly between 0 and 0′? This became known as "Post's problem." The search for such a degree, or proof of its non-existence, was a monumental undertaking. It was finally solved independently by Friedberg and Muchnik in the 1950s, proving that these intermediate r.e. degrees do exist. This is the Friedberg–Muchnik theorem.

Their proofs introduced a technique that has become the cornerstone of r.e. degree construction: the priority method. It's a way to build these degrees, to satisfy a list of requirements, each with its own level of urgency. For instance, to build an r.e. set X between 0 and 0′, you need to satisfy requirements like:

A_e: The oracle machine with index e doesn't compute 0′ from X.
B_e: The Turing machine with index e (no oracle) doesn't compute X.

These requirements are assigned a priority. The proof proceeds in stages, like building something over time. At each stage, numbers might be added to X, or forbidden from entering, to satisfy the requirements. The catch? Satisfying one requirement might break another. That's where priority comes in. Higher priority requirements get precedence. If a lower priority requirement is injured, it might recover later, after the higher priority ones have settled. It's a delicate dance of construction and compromise.

The priority method is a testament to human ingenuity in the face of computational limits. It’s a way of weaving together threads of computability and non-computability, of imposing a fragile order on the chaotic landscape of unsolvability. It’s how we’ve managed to prove so many of the intricate properties of these degrees, by carefully choosing requirements and orchestrating their satisfaction.

For example, constructing a simple (and thus noncomputable r.e.) low X (meaning X′=0′) involves infinitely many stages. At stage n, we have a current state of X (let's call it T_n) and priorities assigned to certain positions. We pick the least important requirement that can be satisfied without upsetting higher priorities. We then update X and adjust priorities to protect the newly satisfied requirement from future interference. It's a process of constant vigilance and adjustment.

The outcome? X is noncomputable because it evades certain computational attempts, and it's simple because it has a specific structure that allows for this evasion. It's low because its jump is 0′. It's a carefully constructed artifact, a piece of mathematical art born from the ashes of impossibility.