Turing Degrees

While computer science can neatly divide problems into 'solvable' and 'unsolvable,' this binary classification hides a surprisingly rich and complex reality. The world of unsolvable problems is not a monolithic wasteland of impossibility; it is a vast universe with its own geography, where some problems are demonstrably 'more unsolvable' than others. But how can we formally measure and compare these different levels of impossibility? This question, first broached by Alan Turing, opens the door to the theory of Turing degrees, a foundational concept in computability theory. This article will guide you through this fascinating landscape. First, in the "Principles and Mechanisms" chapter, we will delve into the core concepts of Turing reducibility, the join, and the jump operator, which together reveal the intricate, branching structure of computational difficulty. Following that, the "Applications and Interdisciplinary Connections" chapter will demonstrate how this theoretical framework becomes a powerful universal language for analyzing complexity in mathematical logic, computational complexity theory, and even the very foundations of mathematics.

Now that we have a taste of the quest to classify unsolvable problems, let's roll up our sleeves and get to the heart of the matter. How, exactly, do we compare two problems that are both, by definition, impossible for a standard computer to solve? It seems like comparing two different kinds of infinity. Yet, mathematicians and logicians, starting with the great Alan Turing himself, have devised an elegant and surprisingly intuitive toolkit for doing just that. Our journey is not just about cataloging problems; it's about discovering a hidden mathematical universe with a rich and beautiful structure.

The first, most fundamental tool is a concept called ​​Turing Reducibility​​. Imagine you are trying to solve a very difficult problem, let's call it $A$. You're stuck. But then, a genie appears and offers you a magic "oracle"—a black box that can instantly answer any question about a different difficult problem, $B$. You can ask it, "Is the number 5 in set $B$?" and it will answer "yes" or "no" in a single step.

If you can write a computer program that successfully solves problem $A$, on the condition that it's allowed to consult this oracle for problem $B$, then we say that ​​$A$ is Turing reducible to $B$​​, written as $A \leq_T B$. In plain English, this means "$A$ is no harder to solve than $B$." If you have a magic solution for $B$, you can manufacture a solution for $A$.

Of course, if we can also show that $B \leq_T A$, it means the two problems are, for all practical purposes, equally difficult. We say they are ​​Turing equivalent​​, written $A \equiv_T B$. All sets that are Turing equivalent to each other are grouped into a single ​​Turing degree​​. A Turing degree is not a problem itself; it's a level of difficulty, a rung on the ladder of computational complexity. The degree of all computable problems (the "solvable" ones) is called ​​$\mathbf{0}$​​.

Now for a bit of magic. Let's take the infamous Halting Problem, $H$. This is the set of all computer programs that halt on an empty input. Suppose we split it in two, almost arbitrarily: let $A$ be the set of numbers $k$ such that the program with code $2k$ halts, and $B$ be the set for codes $2k+1$. It turns out—and this is a deep result—that these two problems, $A$ and $B$, are ​​Turing incomparable​​. An oracle for $A$ doesn't help you solve $B$, and an oracle for $B$ is no help for $A$. They represent distinct, orthogonal kinds of difficulty.

But what if we glue them back together? We can define a new problem, $J$, which is essentially a tagged union of $A$ and $B$. To check if a number is in $J$, you first look at a tag: '0' tells you to check the rest of the number against problem $A$, and '1' tells you to check it against problem $B$. You might think that since $A$ and $B$ are incomparable, $J$ would be some strange new kind of problem. But it's not! It's straightforward to show that $J \equiv_T H$. By simply putting the two pieces of information back together, even though they were "incompatible" on their own, we have reconstructed the full, unabridged difficulty of the original Halting Problem. This simple act of "gluing" problems together is our next key concept.

The "gluing" operation we just saw is formally called the ​​join​​. The join of two sets, $A$ and $B$, is written as $A \oplus B$. It's a new set constructed by putting the elements of $A$ on the even numbers and the elements of $B$ on the odd numbers, just like in our example.

The join is tremendously important because it represents the ​​least upper bound​​ of two Turing degrees. What does that mean? If you have degrees $\mathbf{a}$ and $\mathbf{b}$, their join, $\mathbf{a} \vee \mathbf{b} = \deg(A \oplus B)$, is a new degree that is "above" both of them. More importantly, it's the lowest possible degree that is above both. Think of it like this: if you have two toolboxes, $A$ and $B$, the join $A \oplus B$ is the smallest single toolbox that contains all the tools from both. An oracle for $A \oplus B$ gives you the power of an oracle for $A$ and an oracle for $B$, and nothing more.

This property means that the universe of Turing degrees isn't just a chaotic dust cloud of points. It has an algebraic structure; it's what mathematicians call an ​​upper semi-lattice​​. Any two degrees have a well-defined "sum" or "join" that sits above them.

For a long time, people wondered what this structure looked like. Was it just a simple, straight line? You have the computable problems at degree $\mathbf{0}$. Then perhaps the Halting Problem at degree $\mathbf{0'}$, then something harder, and so on, with every problem neatly fitting somewhere on this line. For any two unsolvable problems, surely one must be harder than the other.

This beautifully simple picture was completely shattered in the 1950s by the ​​Friedberg–Muchnik theorem​​. In one of the great triumphs of computability theory, Richard Friedberg and Albert Muchnik independently proved that there exist two computably enumerable sets whose Turing degrees are incomparable. There is a degree $\mathbf{a}$ and a degree $\mathbf{b}$ such that neither $\mathbf{a} \leq_T \mathbf{b}$ nor $\mathbf{b} \leq_T \mathbf{a}$. The structure is not a line; it's a wildly branching, infinitely complex partial order. The ladder of difficulty has countless, interwoven branches.

If the degrees form such a complex, branching structure, how do we navigate it? In particular, how do we move up? Given a problem, how can we reliably construct a new one that is guaranteed to be harder? The answer is a magnificent operation called the ​​Turing Jump​​.

The jump of a set $A$, denoted $A'$, is simply the Halting Problem relative to A. That is, $A'$ is the set of all oracle Turing machines that halt when they are given access to an oracle for $A$. It answers the question: "What becomes the new Halting Problem if we are given a magic book that solves problem $A$?"

The most crucial property of the jump is that it always increases difficulty. For any set $A$, it is a fundamental theorem that $A$ is strictly less difficult than its own jump: $A <_T A'$. This means $A \leq_T A'$, but $A' \not\leq_T A$. Why? The proof is a beautiful twist on Turing's original diagonalization argument. Imagine you had an oracle for $A'$—a Judge machine that could solve the halting problem for machines with an $A$-oracle. We could then construct a mischievous Paradox machine that uses this Judge. On its own code as input, Paradox asks the Judge what it is going to do. If the Judge says Paradox will halt, it enters an infinite loop. If the Judge says it will loop, it halts. No matter what the Judge says, it's wrong. The only way out of this contradiction is to conclude that the Judge machine cannot exist.

So, the jump is our engine of creation. Starting with the computable sets (degree $\mathbf{0}$), we can jump to get the degree of the Halting Problem, which we call ​​$\mathbf{0'}$​​. We can jump again to get $\mathbf{0''}$, and again for $\mathbf{0'''}$, and so on, creating an infinite ladder of ever-harder problems: $\mathbf{0} <_T \mathbf{0'} <_T \mathbf{0''} <_T \dots$. This ensures there is no "hardest" problem. And best of all, this operation is a natural, canonical feature of computation, not an artifact of how we number our machines.

We've been calling $\mathbf{0'}$ the "degree of the Halting Problem," but what does that power actually feel like? What can you do with an oracle for the Halting Problem that you couldn't do before? A beautiful result known as ​​Shoenfield's Limit Lemma​​ gives us a wonderfully intuitive answer.

A problem is solvable with the help of a $\mathbf{0'}$ oracle if and only if it is ​​limit computable​​. Imagine a computer program that tries to answer a yes/no question. It runs forever, and as it runs, it might change its mind. At stage 1, it says "yes". At stage 10, it changes to "no". At stage 1000, it switches back to "yes". A problem is limit computable if, for any input, this flaky program will eventually settle on a final, unchanging answer.

Without an oracle, you could never be sure if the answer you see is the final one. The program might change its mind a million years from now. An oracle for $\mathbf{0'}$ is precisely the power to "see the limit." It tells you what that final, stable answer will be, without your having to wait an eternity to find out. It is the ability to resolve the infinite behavior of any computable process. In this sense, the degree $\mathbf{0'}$ is precisely the degree of difficulty required to solve any problem that can be approximated by a computable process.

We've now mapped out a landscape of unimaginable complexity. But the true wonder is yet to come. The entire structure we've described—the partial order, the joins, the jumps—doesn't just exist starting from the computable sets. It exists relative to any starting point.

This is the principle of ​​relativization​​. If you take any degree $\mathbf{x}$ and look at the universe of all problems harder than $\mathbf{x}$, that universe has the exact same structure as the entire universe of degrees. It has its own "base level" (which is $\mathbf{x}$), its own jump operator, and its own branching complexities. The structure of Turing degrees is a perfect mathematical fractal: the pattern repeats itself infinitely, no matter where you look.

Let's end on one of the most profound results in the field: ​​Sacks's Jump Theorem​​. We know the jump of a computably enumerable (c.e.) degree must be at or above $\mathbf{0'}$. The theorem asks the reverse question: Can we reach any degree $\mathbf{b}$ above $\mathbf{0'}$ by jumping from some c.e. degree $\mathbf{a}$? The astonishing answer is yes. For any target degree $\mathbf{b} \geq_T \mathbf{0'}$, there exists a c.e. degree $\mathbf{a}$ such that $\mathbf{a}' = \mathbf{b}$.

Think about what this means. The c.e. degrees are a special, in some sense "simpler," class of unsolvable problems. Yet they are so rich and intricately structured that their jumps can land on any predetermined target in the vast universe of degrees above the Halting Problem. There are no "forbidden zones" or "unreachable islands." The c.e. degrees form a foundational continent from which the entire upper cosmos of computability can be explored. It's a stunning testament to the unity and profound depth hidden within the simple question of what a computer can and cannot do.

So, we have journeyed through the intricate machinery of Turing machines and oracle computations to arrive at the concept of Turing degrees. We have seen that not all unsolvable problems are created equal; there exists a vast, beautifully structured hierarchy of "impossibility." But you might be wondering, what is this all for? Is this merely a catalog of curiosities for logicians, a bestiary of abstract computational monsters?

Nothing could be further from the truth. In discovering Turing degrees, we have stumbled upon something akin to a universal ruler. It is a tool that allows us to measure and compare complexity not just within computer science, but across the intellectual landscapes of mathematical logic, computational complexity, and even the very foundations of mathematics itself. We are about to see that the concepts we've developed are not an isolated theory, but a language that reveals deep and often surprising connections between seemingly disparate fields.

Before we venture outwards, let's first appreciate how the theory of Turing degrees provides tools to understand its own structure. The universe of degrees is not a simple, linear ladder. It is a dense, partially ordered wilderness with a rich and fascinating geography.

At the very bottom of this world lies the degree of computable problems, which we denote $\mathbf{0}$. These are the "easy" problems that a standard computer can solve. But what is the defining characteristic of "easy"? Turing degrees give us a wonderfully elegant answer. A problem is computable if and only if it is reducible to every non-computable problem. Think about that for a moment. The truly simple tasks are those that require no help, no matter what powerful (but non-computable) oracle you have access to. They are the common ground of every level of impossibility.

What lies above this ground floor? Is there only one level of impossibility, the one defined by the Halting Problem, $\mathbf{0}'$? For a long time, this was a major open question known as Post's Problem. The answer, when it came, was a resounding "no!" There are, in fact, infinitely many degrees of unsolvability nestled strictly between the computable and the Halting Problem.

The proof of this is a masterpiece of the diagonal method we have seen before. To construct a set $A$ of intermediate degree, we must skillfully weave our way through an infinite list of requirements. We must ensure $A$ is not computable, so we diagonalize against every possible computable set. Simultaneously, we must ensure the Halting Problem isn't computable from $A$, so we diagonalize against every possible oracle machine that could use $A$ to solve it. This construction itself can be analyzed using the tools of computability; we can even count the number of times we must consult the Halting Problem oracle as a guide to satisfy the first $n$ requirements in our construction. The result is not just a proof of existence, but a glimpse into the intricate dance of logic required to navigate the space of uncomputability.

With a feel for the internal structure, we can now turn our gaze outward. We find that the language of Turing degrees provides a powerful lens for examining fundamental questions in mathematical logic and computational complexity.

The Computational Content of Truth and Proof

Mathematical logic is concerned with formal systems, truth, and provability. What does computation have to do with this? As it turns out, everything. Using Gödel numbering, we can encode logical sentences and proofs as numbers, turning questions about logic into questions about sets of numbers. And we can measure the complexity of these sets using Turing degrees.

Consider the complexity of truth itself. What is the computational complexity of the set of all true "for all" statements ($\Pi_1^0$ sentences) of arithmetic? The answer is as profound as it is elegant: the Turing degree of this set is exactly $\mathbf{0}'$, the degree of the Halting Problem. The difficulty of deciding which programs halt is precisely the same as the difficulty of deciding which simple universal truths are true.

This extends beyond provability. We can ask about the complexity of truth itself. Consider a very simple mathematical world: the natural numbers equipped only with the successor function ($S(x) = x+1$) and a predicate that tells us if a number is a perfect square. What is the complexity of the complete theory of this structure—the set of all true first-order sentences about it? One might guess it's simple. But it's not. Its complexity is far beyond the Halting Problem, lying in a higher realm of the analytical hierarchy known as $\Delta_1^1$. This tells us that immense computational complexity can be hiding in the truths of even seemingly simple infinite structures.

Probing the Limits of Efficient Computation

While computability theory asks what is solvable at all, computational complexity theory asks what is solvable efficiently (in polynomial time). This is the land of P vs. NP. Here, too, Turing reducibility plays a starring role, but now with a time limit: polynomial-time Turing reducibility. A problem is NP-hard if every problem in NP can be reduced to it in polynomial time.

The structure of NP-hard problems is central to the P vs. NP question. For example, could an NP-hard problem be "sparse," meaning it has relatively few "yes" instances? Mahaney's Theorem gives a shocking answer: if a sparse language is NP-hard, then P = NP. Assuming the widely held belief that P $\neq$ NP (which is implied by the existence of one-way functions), we must conclude that no sparse language can be NP-hard. This fundamental insight, connecting the "density" of a problem to its computational power, is built upon the idea of Turing reductions.

The tools of computability theory, like oracles and relativization, also serve as powerful thought experiments in complexity. Consider Toda's Theorem, a landmark result showing that the entire Polynomial Hierarchy (a vast generalization of NP) is contained within $P^{\#P}$ (polynomial time with an oracle for counting solutions). A natural question for a computability theorist is: is this proof "black-box"? Does it hold up if we give every machine access to an arbitrary oracle $A$? This is the question of relativization. For Toda's Theorem, the answer is yes: the inclusion $PH^A \subseteq P^{\#P^A}$ holds for any oracle $A$. This tells us the proof's logic is incredibly robust; it doesn't depend on any peculiar properties of our non-oracle world but rather on universal relationships between logical quantifiers and counting that transcend the specific computational substrate.

We have used Turing degrees to measure problems, proofs, and theories. We now arrive at the most breathtaking application of all: using computability to measure the strength of mathematical theorems themselves. This is the goal of a field known as Reverse Mathematics.

The usual mathematical paradigm is to start with axioms and prove theorems. Reverse Mathematics inverts this. It starts with a theorem (like the Bolzano-Weierstrass theorem from analysis) and asks: what is the weakest set of axioms needed to prove it? It's like a chemist carefully titrating a solution to determine the precise concentration of a chemical. Here, the "chemicals" are theorems, and the "concentration" is their logical strength.

How is this done? The key is to build custom-made mathematical universes, called $\omega$-models, and see which theorems hold true inside them. An $\omega$-model is essentially a collection of sets of natural numbers, and its properties are determined by the Turing degrees of the sets it contains. To prove that a theorem $T_1$ does not imply another theorem $T_2$, we must construct a universe that is a model of $T_1$ but not $T_2$.

This is where computability theory becomes the master architect. The construction of these universes is a delicate, high-wire act of forcing and diagonalization. For example, to separate Weak König's Lemma ($\mathrm{WKL}_0$), which states every infinite binary tree has a path, from the Diagonally Non-Recursive principle ($\mathrm{DNR}$), one must build a Turing ideal (a universe closed under reducibility) where $\mathrm{DNR}$ holds but $\mathrm{WKL}_0$ fails. This is achieved by iteratively constructing sets that satisfy the diagonalization requirements of $\mathrm{DNR}$ while simultaneously being designed to avoid being able to compute a path through a specific, cleverly chosen infinite tree.

Properties of Turing degrees, such as being "hyperimmune-free" (meaning any function computable from the set is dominated by a computable function), become crucial building blocks. We can construct entire universes composed only of sets with this property. By analyzing such a universe, we can show that it satisfies some principles (like $\mathrm{WKL}_0$) while failing others, thereby calibrating the logical strength of those principles.

This is the ultimate interdisciplinary connection. The fine-grained structure of unsolvability, the world of Turing degrees that began with Alan Turing's simple question about a machine's ability to halt, has become the essential toolkit for exploring the logical architecture that underpins all of mathematics. It is a journey from a single, concrete problem to a universal framework for understanding the very nature of complexity, proof, and truth.