Computably Enumerable Sets and Turing Degrees
Computably enumerable sets are those whose members can be effectively listed, and Turing degrees rank all sets by relative computability, organizing the landscape of unsolvable problems.
Definition
A set is computably enumerable if some algorithm lists exactly its members; a set is Turing reducible to another if it can be computed using the other as an oracle, and the equivalence classes under mutual reducibility are the Turing degrees, partially ordered by relative computability.
Scope
This topic covers computably enumerable sets and their basic properties, Turing reducibility and the partial order of degrees, the halting set as a complete enumerable set, Post's problem and its resolution by the priority method, and the structural theory of the computably enumerable degrees.
Core questions
- What is the difference between a computable and a merely computably enumerable set?
- How does Turing reducibility compare the difficulty of two sets?
- Are there computably enumerable degrees strictly between the computable sets and the halting problem?
- What is the global structure of the degrees of unsolvability?
Key theories
- Complementation and the halting set
- A set is computable exactly when both it and its complement are computably enumerable, and the halting set is computably enumerable but not computable, the canonical complete enumerable set.
- Post's problem and the priority method
- Post asked whether there are computably enumerable degrees strictly between the computable sets and the halting problem; Friedberg and Muchnik answered yes by inventing the finite-injury priority method.
- Structure of the degrees
- The Turing degrees and the computably enumerable degrees form rich, densely ordered structures studied through advanced priority constructions, revealing intricate definability and embedding properties.
Clinical relevance
The theory of degrees provides the fine classification of unsolvable problems, showing that undecidability comes in infinitely many strictly increasing levels, and the priority method developed to study them is a central proof technique that has influenced reverse mathematics and the analysis of algorithmic randomness.
History
Post introduced computably enumerable sets and posed his problem in 1944, asking whether incomplete noncomputable enumerable degrees exist. Friedberg and Muchnik independently solved it around 1956 with the priority method, which became the principal tool for the deep structural study of the degrees pursued by Sacks, Soare, and many others.
Key figures
- Emil Post
- Richard Friedberg
- Albert Muchnik
- Robert Soare
Related topics
Seminal works
- soare1987
- post1944
- rogers1987
Frequently asked questions
- What is an oracle in computability theory?
- An oracle is an external source that answers membership questions for a fixed set instantly. A machine with an oracle can use those answers during its computation, and Turing reducibility asks whether one set can be computed by a machine equipped with another set as its oracle.
- Why was Post's problem significant?
- It asked whether unsolvability has intermediate levels among computably enumerable sets, between the decidable and the halting problem. The positive answer revealed a fine structure of degrees and required the priority method, a powerful new technique that has shaped the whole subject.