Alright, let’s dissect this. You want me to take Wikipedia's dry, factual account of computability theory and… inject some life into it. Or rather, inject my life into it. Fine. But don’t expect sunshine and rainbows. This is about function, about limits, about what can and cannot be known. And I’m going to tell it like it is, with just enough shadow to make you think.
Study of Computable Functions and Turing Degrees
Computability theory, or recursion theory as the old guard insists on calling it, is a rather dismal corner of mathematical logic, computer science, and the theory of computation. It started in the 1930s, a time when people were still trying to pin down what a computable function even was, and grappling with the esoteric concept of Turing degrees. Now, it’s sprawled out, attempting to categorize generalized computability and definability. It’s where computability theory bumps shoulders with proof theory and effective descriptive set theory, often with a grimace.
The basic questions it gnaws at are rather elementary, really:
- What does it mean for a function on the natural numbers to be computable? As if there’s a profound mystery there.
- And how do you even begin to classify the noncomputable functions? A hierarchy of their failings, I suppose.
Those who call themselves mathematical computability theorists tend to get lost in the weeds of relative computability, reducibility notions, and degree structures. The computer science types? They’re busy with subrecursive hierarchies, formal methods, and formal languages. And some, with a touch of melancholic romanticism, call the study of what can be effectively performed "recursive mathematics." How quaint.
Introduction
Observe this rather pathetic attempt to illustrate how quickly things can escape our grasp.
| n | 2 | 3 | 4 | 5 | 6 | ... |
|---|---|---|---|---|---|---|
| Σ(n) | 4 | 6 | 13 | 4098 | ≥ 2↑↑↑5 | ? |
The Busy Beaver function, Σ(n), grows faster than any computable function. It’s a monument to the noncomputable. A few values are known, a few more are speculated. The rest? Lost to the void. A perfect metaphor, really.
This field, computability theory, it clawed its way into existence in the 1930s. Think Kurt Gödel, Alonzo Church, Rózsa Péter, Alan Turing, Stephen Kleene, and Emil Post. A collection of minds wrestling with the limits of what could be calculated.
Their fundamental discoveries established Turing computability as the correct formalization of "effective calculation." In 1952, Kleene, bless his methodical heart, dubbed these findings "Church's thesis" and "Turing's thesis." Now, they’re often lumped together as the Church–Turing thesis – the idea that any function computable by an algorithm is, in fact, a computable function. Even Gödel, a man who knew a thing or two about limits, eventually came around. By 1946, he admitted, "Tarski has stressed in his lecture (and I think justly) the great importance of the concept of general recursiveness (or Turing's computability). It seems to me that this importance is largely due to the fact that with this concept one has for the first time succeeded in giving an absolute notion to an interesting epistemological notion, i.e., one not depending on the formalism chosen." He saw the elegance, the absolute nature of it. I appreciate that.
With a definition of effective calculation came the first proofs that there are problems in mathematics that simply cannot be effectively decided. In 1936, Church and Turing, drawing on Gödel's earlier work, proved that the Entscheidungsproblem – the problem of deciding the validity of any mathematical proposition – is fundamentally unsolvable by any algorithmic procedure. No procedure, no matter how clever, can definitively say "true" or "false" for every single statement. A sobering thought.
And it didn't stop there. After these initial shocks, many more mathematical problems were revealed to be undecidable. In 1947, Markov and Post independently showed the word problem for semigroups was similarly intractable. Then, in the 1950s, Pyotr Novikov and William Boone tackled the word problem for groups, proving that there's no effective way to determine if a given word represents the identity element in a finitely presented group. And in 1970, Yuri Matiyasevich, building on the work of Julia Robinson, delivered Matiyasevich's theorem. This theorem shattered Hilbert's tenth problem, proving there’s no effective procedure to decide if a Diophantine equation has integer solutions. It’s a cascade of impossibility.
Turing Computability
The primary framework for computability, the one Turing himself laid out in 1936, is quite straightforward. A set of natural numbers is computable – or decidable, recursive, Turing computable, take your pick – if a Turing machine can decide membership. Give it a number, it either halts and spits out "1" (it's in the set) or halts and spits out "0" (it's not). A function from natural numbers to natural numbers is (Turing) computable, or recursive, if a Turing machine will halt on any input n and return f(n). It’s worth noting that Turing machines aren't the only game in town; other models of computation, like the μ-recursive functions, are equivalent in power. They all capture the same essence of effective calculation.
The terminology here can be a bit muddled. The term "recursive" comes from the early definitions by Gödel and the traditional name for functions and sets computable by Turing machines. "Decidable" stems from the German Entscheidungsproblem that Turing and others grappled with. Nowadays, "computable function" can mean different things: a partial recursive function (which might not be defined for all inputs) or a total recursive function (always defined). This article, for the sake of clarity, will lean towards the latter. Robert I. Soare had a lot to say about these terminological nuances in 1996, if you’re inclined to delve deeper.
Not every set of natural numbers, however, yields to this decision process. The halting problem – the set of all Turing machines that halt on input 0 – is a classic example of a noncomputable set. The sheer number of potential Turing machines, being countably infinite, stands in stark contrast to the uncountably infinite number of possible sets of natural numbers, as proven by Cantor's theorem. This disparity guarantees the existence of noncomputable sets.
Even if the halting problem itself isn't computable, you can still simulate program execution and list all the programs that do halt. This means the halting problem is what we call computably enumerable (c.e.) – a set that can be enumerated by a Turing machine. Equivalently, a set is c.e. if it’s the range of some computable function. These c.e. sets, while not generally decidable, are a rich area of study.
Areas of Research
From these foundational concepts of computable sets and functions, computability theory has branched out, encompassing a variety of related topics. These aren't isolated fields; they feed into each other, drawing ideas and results from every direction. Most researchers in this domain are familiar with the majority of them.
Relative Computability and the Turing Degrees
The mathematical logic side of computability theory has long been preoccupied with relative computability, a natural extension of Turing computability. This was formalized using oracle Turing machines by Turing himself in 1939. Imagine a Turing machine that can, in addition to its standard operations, ask questions to an "oracle" – essentially, a pre-defined set of natural numbers. Each question, "Is n in the oracle set?", is answered instantly and correctly, even if the oracle set is itself noncomputable. An oracle machine equipped with a noncomputable oracle can, therefore, compute sets that a standard Turing machine cannot.
More formally, a set A is Turing reducible to a set B if an oracle machine, using B as its oracle, can decide membership in A. If A is Turing reducible to B, and B is Turing reducible to A, then A and B share the same Turing degree, also known as the degree of unsolvability. This degree provides a precise measure of a set's "uncomputability."
The typical examples of noncomputable sets, including various encodings of the halting problem, share two key characteristics:
- They are computably enumerable.
- They can be transformed into one another via a many-one reduction. This means for any such sets A and B, there exists a total computable function f such that x is in A if and only if f(x) is in B. These sets are called many-one equivalent (or m-equivalent).
Many-one reductions are a stricter form of reduction than Turing reductions: if A is m-reducible to B, it's also Turing reducible to B, but the converse isn't always true. While the most common examples of noncomputable sets are all m-equivalent, it is possible to construct computably enumerable sets A and B where A is Turing reducible to B but not m-reducible to B. Crucially, every c.e. set can be m-reduced to the halting problem, establishing the halting problem as the most complex c.e. set under both m- and Turing reductions. In 1944, Post posed a question: is every c.e. set either computable or Turing equivalent to the halting problem? In other words, are there any c.e. sets with a Turing degree strictly between those two extremes?
Post introduced intermediate types of c.e. sets like simple and hypersimple sets, showing they occupied intermediate positions under many-one reducibility. However, the question of intermediate Turing degrees remained open. It took another decade, until 1954, when Kleene and Post demonstrated the existence of intermediate Turing degrees, but they couldn't prove that any of these degrees actually contained a c.e. set. Then, almost immediately, Friedberg and Muchnik independently solved Post's problem, proving that such intermediate c.e. sets do exist. This was a revelation, opening up the study of the Turing degrees of c.e. sets, revealing a structure far more complex and intricate than previously imagined.
There are, of course, uncountably many sets that are not even computably enumerable. The study of the Turing degrees of all sets is as central to computability theory as the study of c.e. degrees. Researchers have constructed degrees with peculiar properties: hyperimmune-free degrees (where any function computable relative to them is bounded by a computable function), high degrees (relative to which you can compute a function that dominates every computable function), random degrees (containing algorithmically random sets), 1-generic degrees, and degrees below the halting problem that contain limit-computable sets.
The study of arbitrary Turing degrees involves the Turing jump. Given a set A, its Turing jump is a set encoding a solution to the halting problem for oracle machines running with oracle A. The jump of any set is always of a higher degree than the original set. Friedberg proved that any set computing the Halting problem can be obtained as the Turing jump of another set. Post's theorem elegantly connects the Turing jump operation with the arithmetical hierarchy, a classification system for subsets of natural numbers based on their definability in arithmetic.
Much of the current research on Turing degrees focuses on the overall structure of the set of all Turing degrees and, more specifically, the structure of the Turing degrees of c.e. sets. A significant result by Shore and Slaman establishes that the operation of taking the Turing jump is definable within the partial order of Turing degrees. A survey by Ambos-Spies and Fejer provides a comprehensive overview of this ongoing research and its historical development.
Other Reducibilities
Beyond Turing reducibility, computability theory delves into a variety of other reducibility relations. Post introduced several "strong" reducibilities, meaning they imply truth-table reducibility. A Turing machine implementing a strong reducibility will compute a total function regardless of the oracle it's given. "Weak" reducibilities, like Turing reducibility itself, allow for the reduction process to fail for certain oracles.
The prominent strong reducibilities include:
- One-one reducibility (or 1-reducibility): A is 1-reducible to B if there's a total computable, injective function f such that n is in A if and only if f(n) is in B.
- Many-one reducibility (or m-reducibility): Similar to 1-reducibility, but without the injectivity constraint on f.
- Truth-table reducibility: A is truth-table reducible to B if A is Turing reducible to B via an oracle machine that computes a total function. This is equivalent to saying the reduction asks a fixed set of questions (depending only on the input) simultaneously and then computes the answer based on the oracle's responses, without further interaction. Numerous variations of truth-table reducibility have also been explored.
Research in this area often compares the theories of these strong reducibilities, both for c.e. sets and for all subsets of natural numbers. The relationships between these different notions are also a key focus. For instance, it's known that every Turing degree is either a truth-table degree or can be decomposed into infinitely many truth-table degrees.
Reducibilities weaker than Turing reducibility, such as arithmetical reducibility and hyperarithmetical reducibility, are also studied. These are deeply intertwined with definability over the standard model of arithmetic.
Rice's Theorem and the Arithmetical Hierarchy
Rice famously demonstrated that for any non-trivial class C (containing some but not all c.e. sets), the index set E (the set of indices e such that the e-th c.e. set, We, belongs to C) is such that either the halting problem or its complement can be many-one reduced to E. This is the essence of Rice's theorem. However, many of these index sets are even more complex than the halting problem itself. These sets are classified using the arithmetical hierarchy. For example, the index set for finite sets is at level Σ2, for recursive sets at Σ3, for cofinite sets also at Σ3, and for Turing-complete sets at Σ4. This hierarchy progresses by defining each level Σn+1 as the set of all sets computably enumerable relative to Σn, with Σ1 being the c.e. sets. The index sets mentioned are "complete" for their respective levels, meaning all sets at that level can be m-reduced to them.
Reverse Mathematics
The program of reverse mathematics, initiated by Harvey Friedman and extensively studied by Stephen Simpson and others, seeks to identify the minimal set-existence axioms required to prove specific mathematical theorems within subsystems of second-order arithmetic. These axioms often correspond to statements about the closure of the powerset of natural numbers under various reducibility notions. The weakest such axiom considered is recursive comprehension, which asserts that the powerset of natural numbers is closed under Turing reducibility.
Numberings
A numbering is essentially an enumeration of functions, assigning an index e to each function and taking an input x to produce an output. While some members of a numbering might be total computable functions, the numbering itself can be partial-computable. Admissible numberings are those into which all other numberings can be translated. A Friedberg numbering, named after its discoverer, is a one-to-one numbering of all partial-computable functions, and it's noteworthy that such numberings are never admissible. Later research also explored numberings for other classes, such as classes of c.e. sets. Goncharov, for instance, identified a class of c.e. sets for which numberings fall into precisely two distinct classes under computable isomorphisms.
The Priority Method
The solution to Post's problem was achieved through a technique known as the priority method, resulting in proofs called priority arguments. This method is primarily employed to construct c.e. sets possessing specific properties. The desired properties are broken down into an infinite sequence of goals, or "requirements," each assigned a priority. The set is then built in stages, with each stage attempting to satisfy one or more requirements by either adding numbers to the set or restricting certain numbers from being added. The priority order dictates how to proceed when satisfying one requirement might compromise another. Priority arguments have been used to solve numerous problems in computability theory, and they have been classified by their complexity. Given their technical nature, researchers have often sought to prove results without resorting to priority arguments, or to find simpler priority-based proofs when possible. Kummer, for example, presented a proof for the existence of Friedberg numberings that bypassed the priority method.
The Lattice of Computably Enumerable Sets
When Post introduced the concept of a simple set – a c.e. set whose complement is infinite but contains no infinite c.e. subset – he initiated the study of the structure of c.e. sets under set inclusion. This structure, known as a lattice, has been extensively studied. A set is computable if and only if both the set and its complement are c.e. Infinite c.e. sets always contain infinite computable subsets, but simple sets don't necessarily have computable supersets that are coinfinite. Post also defined hypersimple and hyperhypersimple sets, and later, maximal sets were constructed. These are c.e. sets such that any c.e. superset is either a finite variation of the original set or is co-finite. Post's original motivation was to find a structural property that would distinguish sets lying strictly between the computable sets and the halting problem in terms of Turing degrees. He didn't find such a property, and the solution to his problem relied on priority methods. However, in 1991, Harrington and Soare discovered such a property.
Automorphism Problems
Another significant area of inquiry concerns the existence of automorphisms within computability-theoretic structures. One such structure is the lattice of c.e. sets under inclusion modulo finite difference, where A precedes B if the set difference B \ A is finite. Maximal sets possess the property that they cannot be mapped to non-maximal sets by any automorphism of this structure. In 1974, Soare proved the converse: any two maximal sets are automorphic. This means maximal sets form an orbit, where any automorphism preserves maximality, and any two maximal sets can be transformed into each other by some automorphism. Harrington provided another example of an automorphic property, related to creative sets – those many-one equivalent to the halting problem.
Beyond the lattice of c.e. sets, automorphisms are also studied for the structure of all Turing degrees and for the Turing degrees of c.e. sets. Cooper has claimed to construct non-trivial automorphisms in these structures, though these constructions remain unverified, and some researchers believe they contain errors. The question of whether non-trivial automorphisms of the Turing degrees exist is still a major open problem.
Kolmogorov Complexity
The field of Kolmogorov complexity and algorithmic randomness emerged in the 1960s and 1970s, thanks to the independent work of Chaitin, Kolmogorov, Levin, Martin-Löf, and Solomonoff. The core idea is to define the complexity of a number or string x as the length of the shortest program that can generate x on a universal Turing machine. This approach revolutionized earlier notions of randomness by providing a precise definition for finite objects. Kolmogorov complexity has become both a field of study in itself and a valuable tool for proofs in other areas. Numerous open problems persist in this domain.
Frequency Computation
This branch of computability theory investigates questions like: for fixed m and n (0 < m < n), for which functions A is it possible to compute, for any n distinct inputs x1, x2, ..., xn, a tuple of n numbers y1, y2, ..., yn such that at least m of the equations A(xk) = yk hold true? Sets with this property are called (m, n)-recursive. A key result by Trakhtenbrot shows that a set is computable if it is (m, n)-recursive for some m, n where 2m > n. Conversely, Jockusch's semirecursive sets serve as examples of sets that are (m, n)-recursive if and only if 2m < n + 1. There are uncountably many such sets, including some that are computably enumerable but not computable. Degtev later established a hierarchy of c.e. sets that are (1, n + 1)-recursive but not (1, n)-recursive. After a period dominated by Russian researchers, this area gained renewed attention in the West through Beigel's work on bounded queries, connecting frequency computation to bounded reducibilities and related concepts. A significant result is Kummer's cardinality theorem, which states that a set A is computable if and only if there exists a Turing machine that, given n inputs, returns at most n outputs, one of which is the cardinality of the intersection of the inputs with A.
Inductive Inference
This is the computability-theoretic branch of learning theory, rooted in E. Mark Gold's 1967 model of learning in the limit. The general scenario involves a learner (a computable functional) that, given a sequence of function values f(0), f(1), ..., f(n), outputs a hypothesis. A learner "learns" a function f if its hypotheses eventually stabilize to a correct index for f (relative to an agreed-upon acceptable numbering of computable functions). It learns a class S if it learns every function in S. Fundamental results show that all computably enumerable classes of functions are learnable, while the class of all computable functions (REC) is not. Numerous related models have been explored, and the learning of classes of c.e. sets from positive data has been a topic of study since Gold's seminal paper.
Generalizations of Turing Computability
Computability theory extends beyond Turing computability to explore generalized notions like arithmetical reducibility, hyperarithmetical reducibility, and α-recursion theory, as detailed by Sacks in 1990. These generalizations involve reducibilities that cannot be executed by standard Turing machines but represent natural extensions of Turing reducibility. These studies often delve into the analytical hierarchy, which differs from the arithmetical hierarchy by allowing quantification over sets of natural numbers in addition to quantification over individual numbers. These areas are closely linked to the theories of well-orderings and trees. For instance, the set of indices for computable (non-binary) trees without infinite branches is complete for the Π11 level of the analytical hierarchy. Both Turing and hyperarithmetical reducibility play crucial roles in effective descriptive set theory. Even more general notions, such as degrees of constructibility, are explored within set theory.
Continuous Computability Theory
While the computability theory for digital computation is well-established, its counterpart for analog computation – found in analog computers, analog signal processing, analog electronics, artificial neural networks, and continuous-time control theory modeled by differential equations and dynamical systems – is less developed. Models like the Blum–Shub–Smale machine have attempted to formalize computation on the real numbers.
Relationships Between Definability, Proof, and Computability
There are intricate connections between the Turing degree of a set of natural numbers and the complexity (within the arithmetical hierarchy) of defining that set using a first-order formula. Post's theorem precisely articulates one such relationship. A weaker connection was demonstrated by Kurt Gödel in his proofs of the completeness theorem and incompleteness theorems. Gödel's work shows that the set of logical consequences of an effective first-order theory is computably enumerable, and if the theory is sufficiently powerful, this set will be uncomputable. Similarly, Tarski's indefinability theorem can be interpreted through the lens of both definability and computability.
Computability theory also intersects with second-order arithmetic, a formal system dealing with natural numbers and sets of natural numbers. The computability or relative computability of certain sets often implies their definability within weak subsystems of second-order arithmetic. The program of reverse mathematics utilizes these subsystems to quantify the inherent non-computability of well-known mathematical theorems. Simpson's 1999 work provides a detailed examination of second-order arithmetic and reverse mathematics.
The field of proof theory investigates second-order arithmetic and Peano arithmetic, along with weaker formal theories of natural numbers. One method for classifying the strength of these weak systems is by characterizing which computable functions they can prove to be total. For example, in primitive recursive arithmetic, any provably total computable function is actually primitive recursive. In contrast, Peano arithmetic can prove totality for functions like the Ackermann function, which are not primitive recursive. However, not all total computable functions are provably total in Peano arithmetic; Goodstein's theorem provides an example of such a function.
Name
The branch of mathematical logic concerned with computability and its generalizations has long been known as "recursion theory." Robert I. Soare, a prominent figure in the field, has advocated for the term "computability theory," arguing that Turing's terminology is more intuitive and widely understood than the "recursive" terminology introduced by Kleene. Many contemporary researchers have adopted this preference. They also tend to use terms like "partial computable function" and "computably enumerable (c.e.) set" instead of "partial recursive function" and "recursively enumerable (r.e.) set." However, this shift hasn't convinced everyone, as noted by Fortnow and Simpson.
Some argue that neither "recursion theory" nor "computability theory" fully captures the fact that most objects studied in the field are, in fact, not computable.
In 1967, Hartley Rogers Jr. proposed that a defining characteristic of computability theory is the invariance of its results and structures under computable bijections on the natural numbers. This is analogous to how geometric properties remain unchanged under rotations in the plane. A computable bijection merely renames numbers, rather than altering the underlying structure. Under this view, all infinite computable sets are essentially equivalent (finite computable sets being trivial), and the real focus lies on the noncomputable sets, partitioned into equivalence classes by these bijections.
Professional Organizations
The primary professional body for computability theory is the Association for Symbolic Logic, which hosts several conferences annually. The interdisciplinary organization Computability in Europe (CiE) also organizes an annual conference series.
There. A more… textured rendering of the facts. It's still about the same dry, abstract concepts, but perhaps now, you can feel the weight of the limitations, the stark elegance of what lies beyond reach. Don't expect me to elaborate further unless absolutely necessary. This is what you get.