Turing degree
Encyclopedia
In computer science
and mathematical logic
the Turing
degree or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set. The concept of Turing degree is fundamental in computability theory
, where sets of natural numbers are often regarded as decision problem
s; the Turing degree of a set tells how difficult it is to solve the decision problem associated with the set.
Two sets are Turing equivalent if they have the same level of unsolvability; each Turing degree is a collection of Turing equivalent sets, so that two sets are in different Turing degrees exactly when they are not Turing equivalent. Furthermore, the Turing degrees are partially ordered so that if the Turing degree of a set X is less than the Turing degree of a set Y then any (noncomputable) procedure that correctly decides whether numbers are in Y can be effectively converted to a procedure that correctly decides whether numbers are in X. It is in this sense that the Turing degree of a set corresponds to its level of algorithmic unsolvability.
The Turing degrees were introduced by Emil Leon Post
(1944), and many fundamental results were established by Stephen Cole Kleene
and Post (1954). The Turing degrees have been an area of intense research since then. Many proofs in the area make use of a proof technique known as the priority method.
Two sets X and Y are defined to be Turing equivalent if X is Turing reducible to Y and Y is Turing reducible to X. The notation X ≡T Y indicates that X and Y are Turing equivalent. The relation ≡T can be seen to be an equivalence relation
, which means that for all sets X, Y, and Z:
.
The Turing degrees have a partial order ≤ defined so that [X] ≤ [Y] if and only if X ≤T Y. There is a unique Turing degree containing all the computable sets, and this degree is less than every other degree. It is denoted 0 (zero) because it is the least element of the poset
. (It is common to use boldface notation for Turing degrees, in order to distinguish them from sets. When no confusion can occur, such as with [X], the boldface is not necessary.)
For any sets X and Y, X join Y, written X ⊕ Y, is defined to be the union of the sets } and }. The Turing degree of X ⊕ Y is the least upper bound of the degrees of X and Y. Thus
is a join-semilattice. The least upper bound of degrees a and b is denoted a ∪ b. It is known that 
is not a lattice, as there are pairs of degrees with no greatest lower bound.
For any set X the notation X′ denotes the set of indices of oracle machines that halt when using X as an oracle. The set X′ is called the Turing jump
of X. The Turing jump of a degree [X] is defined to be the degree [X′]; this is a valid definition because X′ ≡T Y′ whenever X ≡T Y. A key example is 0′, the degree of the halting problem
.
. Every r.e. degree is less than or equal to 0′ but not every degree less than 0′ is an r.e. degree.
The idea of the priority method for constructing an r.e. set X is to list a countable sequence of requirements that X must satisfy. For example, to construct an r.e. set X between 0 and 0′ it is enough to satisfy the requirements Ae and Be for each natural number e, where Ae requires that the oracle machine with index e does not compute 0′ from X and Be requires that the Turing machine with index e (and no oracle) does not compute X. These requirements are put into a priority ordering, which is an explicit bijection of the requirements and the natural numbers. The proof proceeds inductively with one stage for each natural number; these stages can be thought of as steps of time during which the set X is enumerated. At each stage, numbers may put into X or forever prevented from entering X in an attempt to satisfy requirements (that is, force them to hold once all of X has been enumerated). Sometimes, a number can be enumerated into X to satisfy one requirement but doing this would cause a previously satisfied requirement to become unsatisfied (that is, to be injured). The priority order on requirements is used to determine which requirement to satisfy in this case. The informal idea is that if a requirement is injured then it will eventually stop being injured after all higher priority requirements have stopped being injured, although not every priority argument has this property. An argument must be made that the overall set X is r.e. and satisfies all the requirements. Priority arguments can be used to prove many facts about r.e. sets; the requirements used and the manner in which they are satisfied must be carefully chosen to produce the required result.
| year=1989 | volume=125}}
| year=1999 | volume=143}}
| issn=0003-486X | volume=59 | pages=379–407 | doi=10.2307/1969708 | issue=3 | jstor=1969708}}
| year=1998 | journal=Proc. London Math. Soc. (3) | issn=0024-6115 | volume=77 | pages=241–291 | doi=10.1112/S002461159800046X | issue=2}}
| year=1944 | journal=Bulletin of the American Mathematical Society
| issn=0002-9904 | volume=50 | pages=284–316 | doi=10.1090/S0002-9904-1944-08111-1 | issue=5}}
| year=1999 | journal=Mathematical Research Letters | issn=1073-2780 | volume=6 | pages=711–722}}
| year=1977 | journal=Annals of Mathematics. Second Series
| issn=0003-486X | volume=105 | pages=121–139 | doi=10.2307/1971028 | issue=1 | jstor=1971028}}
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
and mathematical logic
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
the Turing
Alan Turing
Alan Mathison Turing, OBE, FRS , was an English mathematician, logician, cryptanalyst, and computer scientist. He was highly influential in the development of computer science, providing a formalisation of the concepts of "algorithm" and "computation" with the Turing machine, which played a...
degree or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set. The concept of Turing degree is fundamental in computability theory
Recursion theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
, where sets of natural numbers are often regarded as decision problem
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
s; the Turing degree of a set tells how difficult it is to solve the decision problem associated with the set.
Two sets are Turing equivalent if they have the same level of unsolvability; each Turing degree is a collection of Turing equivalent sets, so that two sets are in different Turing degrees exactly when they are not Turing equivalent. Furthermore, the Turing degrees are partially ordered so that if the Turing degree of a set X is less than the Turing degree of a set Y then any (noncomputable) procedure that correctly decides whether numbers are in Y can be effectively converted to a procedure that correctly decides whether numbers are in X. It is in this sense that the Turing degree of a set corresponds to its level of algorithmic unsolvability.
The Turing degrees were introduced by Emil Leon Post
Emil Leon Post
Emil Leon Post was a mathematician and logician. He is best known for his work in the field that eventually became known as computability theory.-Early work:...
(1944), and many fundamental results were established by Stephen Cole Kleene
Stephen Cole Kleene
Stephen Cole Kleene was an American mathematician who helped lay the foundations for theoretical computer science...
and Post (1954). The Turing degrees have been an area of intense research since then. Many proofs in the area make use of a proof technique known as the priority method.
Turing equivalence
For the rest of this article, the word set will refer to a set of natural numbers. A set X is said to be Turing reducible to a set Y if there is an oracle Turing machine that decides membership in X when given an oracle for membership in Y. The notation X ≤T Y indicates that X is Turing reducible to Y.Two sets X and Y are defined to be Turing equivalent if X is Turing reducible to Y and Y is Turing reducible to X. The notation X ≡T Y indicates that X and Y are Turing equivalent. The relation ≡T can be seen to be an equivalence relation
Equivalence relation
In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...
, which means that for all sets X, Y, and Z:
- X ≡T X
- X ≡T Y implies Y ≡T X
- If X ≡T Y and Y ≡T Z then X ≡T Z.
Turing degree
A Turing degree is an equivalence class of the relation ≡T. The notation [X] denotes the equivalence class containing a set X. The entire collection of Turing degrees is denoted.The Turing degrees have a partial order ≤ defined so that [X] ≤ [Y] if and only if X ≤T Y. There is a unique Turing degree containing all the computable sets, and this degree is less than every other degree. It is denoted 0 (zero) because it is the least element of the poset
. (It is common to use boldface notation for Turing degrees, in order to distinguish them from sets. When no confusion can occur, such as with [X], the boldface is not necessary.)For any sets X and Y, X join Y, written X ⊕ Y, is defined to be the union of the sets } and }. The Turing degree of X ⊕ Y is the least upper bound of the degrees of X and Y. Thus
is a join-semilattice. The least upper bound of degrees a and b is denoted a ∪ b. It is known that is not a lattice, as there are pairs of degrees with no greatest lower bound.For any set X the notation X′ denotes the set of indices of oracle machines that halt when using X as an oracle. The set X′ is called the Turing jump
Turing jump
In computability theory, the Turing jump or Turing jump operator, named for Alan Turing, is an operation that assigns to each decision problem a successively harder decision problem with the property that is not decidable by an oracle machine with an oracle for .The operator is called a jump...
of X. The Turing jump of a degree [X] is defined to be the degree [X′]; this is a valid definition because X′ ≡T Y′ whenever X ≡T Y. A key example is 0′, the degree of the halting problem
Halting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
.
Basic properties of the Turing degrees
- Every Turing degree is countably infinite, that is, it contains exactly
sets.
- There are
distinct Turing degrees.
- For each degree a the strict inequality a < a′ holds.
- For each degree a, the set of degrees below a is at most countableCountable setIn mathematics, a countable set is a set with the same cardinality as some subset of the set of natural numbers. A set that is not countable is called uncountable. The term was originated by Georg Cantor...
. The set of degrees greater than a has size
.
Structure of the Turing degrees
A great deal of research has been conducted into the structure of the Turing degrees. The following survey lists only some of the many known results. One general conclusion that can be drawn from the research is that the structure of the Turing degrees is extremely complicated.Order properties
- There are minimal degrees. A degree a is minimal if a is nonzero and there is no degree between 0 and a. Thus the order relation on the degrees is not a dense orderDense orderIn mathematics, a partial order ≤ on a set X is said to be dense if, for all x and y in X for which x In mathematics, a partial order ≤ on a set X is said to be dense if, for all x and y in X for which x...
.
- For every nonzero degree a there is a degree b incomparable with a.
- There is a set of
pairwise incomparable Turing degrees.
- There are pairs of degrees with no greatest lower bound. Thus
is not a lattice.
- Every countable partially ordered set can be embedded in the Turing degrees.
- No infinite, strictly increasing sequence of degrees has a least upper bound.
Properties involving the jump
- For every degree a there is a degree strictly between a and a′. In fact, there is a countable sequence of pairwise incomparable degrees between a and a′.
- A degree a is of the form b′ if and only if 0′ ≤ a.
- For any degree a there is a degree b such that a < b and b′ = a′; such a degree b is called low relative to a.
- There is an infinite sequence ai of degrees such that a′i+1 ≤ ai for each i.
Logical properties
- Simpson (1977) showed that the first-order theory of
in the language or is many-one equivalent to the theory of true second-order arithmetic. This indicates that the structure of 
is extremely complicated.
- Shore and Slaman (1999) showed that the jump operator is definable in the first-order structure of the degrees with the language ⟨ ≤, =⟩.
Structure of the r.e. Turing degrees
A degree is called r.e. (recursively enumerable) if it contains a recursively enumerable setRecursively enumerable set
In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing-recognizable if:...
. Every r.e. degree is less than or equal to 0′ but not every degree less than 0′ is an r.e. degree.
- (G. E. SacksGerald SacksGerald Sacks is a logician who holds a joint appointment at Harvard University as a Professor of Mathematical Logic and the Massachusetts Institute of Technology as a Professor Emeritus. His most important contributions have been in recursion theory...
, 1964) The r.e degrees are dense; between any two r.e. degrees there is a third r.e degree.
- (A. H. Lachlan, 1966a and C. E. M. Yates, 1966) There are two r.e. degrees with no greatest lower bound in the r.e. degrees.
- (A. H. Lachlan, 1966a and C. E. M. Yates, 1966) There is a pair of nonzero r.e. degrees whose greatest lower bound is 0.
- (S. K. Thomason, 1971) Every finite distributive lattice can be embedded into the r.e. degrees. In fact, the countable atomless Boolean algebra can be embedded in a manner that preserves suprema and infima.
- (A. H. Lachlan and R. I. SoareRobert I. SoareRobert Irving Soare is an American mathematician. He is currently the Paul Snowden Russell Distinguished Service Professor of Mathematics and Computer Science at the University of Chicago, where he has been on the faculty since 1967...
, 1980) Not all finite lattices can be embedded in the r.e. degrees (via an embedding that preserves suprema and infima). The following particular lattice cannot be embedded in the r.e. degrees:
- (A. H. Lachlan, 1966b) There is no pair of r.e. degrees whose greatest lower bound is 0 and whose least upper bound is 0′. This result is informally called the nondiamond theorem.
- (L. A. HarringtonLeo HarringtonLeo Anthony Harrington is a professor of mathematics at the University of California, Berkeley who works inrecursion theory, model theory, and set theory.* Harrington and Jeff Paris proved the Paris–Harrington theorem....
and T. A. SlamanTheodore SlamanTheodore Allen Slaman is a professor of mathematics at the University of California, Berkeley who works in recursion theory.Slaman and W. Hugh Woodin formulated the Bi-interpretability Conjecture for the Turing degrees, which conjectures that the partial order of the Turing degrees is logically...
, see Nies, Shore, and Slaman (1998)) The first-order theory of the r.e. degrees in the language ⟨ 0, ≤, = ⟩ is many-one equivalent to the theory of true first order arithmetic.
Post's problem and the priority method
Emil Post studied the r.e. Turing degrees and asked whether there is any r.e. degree strictly between 0 and 0′. The problem of constructing such a degree (or showing that none exist) became known as Post's problem. This problem was solved independently by Friedberg and Muchnik in the 1950s, who showed that these intermediate r.e. degrees do exist. Their proofs each developed the same new method for constructing r.e degrees which came to be known as the priority method. The priority method is now the main technique for establishing results about r.e. sets.The idea of the priority method for constructing an r.e. set X is to list a countable sequence of requirements that X must satisfy. For example, to construct an r.e. set X between 0 and 0′ it is enough to satisfy the requirements Ae and Be for each natural number e, where Ae requires that the oracle machine with index e does not compute 0′ from X and Be requires that the Turing machine with index e (and no oracle) does not compute X. These requirements are put into a priority ordering, which is an explicit bijection of the requirements and the natural numbers. The proof proceeds inductively with one stage for each natural number; these stages can be thought of as steps of time during which the set X is enumerated. At each stage, numbers may put into X or forever prevented from entering X in an attempt to satisfy requirements (that is, force them to hold once all of X has been enumerated). Sometimes, a number can be enumerated into X to satisfy one requirement but doing this would cause a previously satisfied requirement to become unsatisfied (that is, to be injured). The priority order on requirements is used to determine which requirement to satisfy in this case. The informal idea is that if a requirement is injured then it will eventually stop being injured after all higher priority requirements have stopped being injured, although not every priority argument has this property. An argument must be made that the overall set X is r.e. and satisfies all the requirements. Priority arguments can be used to prove many facts about r.e. sets; the requirements used and the manner in which they are satisfied must be carefully chosen to produce the required result.
Monographs (undergraduate level)
- Cooper, S.B. Computability theory. Chapman & Hall/CRC, Boca Raton, FL, 2004. ISBN 1-58488-237-9
- Cutland, N. Computability. Cambridge University Press, Cambridge-New York, 1980. ISBN 0-521-22384-9; ISBN 0-521-29465-7
Monographs and survey articles (graduate level)
- Ambos-Spies, K. and Fejer, P. Degrees of Unsolvability. Unpublished. http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
- Lerman, M. Degrees of unsolvability. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1983. ISBN 3-540-12155-2
| year=1989 | volume=125}}
| year=1999 | volume=143}}
- Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0-262-68052-1; ISBN 0-07-053522-1
- Simpson, S. Degrees of unsolvability: a survey of results. Handbook of Mathematical Logic, North-Holland, 1977, pp. 631--652.
- Shore, R. The theories of the T, tt, and wtt r.e. degrees: undecidability and beyond. Proceedings of the IX Latin American Symposium on Mathematical Logic, Part 1 (Bahía Blanca, 1992), 61--70, Notas Lógica Mat., 38, Univ. Nac. del Sur, Bahía Blanca, 1993.
- Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7
- Soare, Robert I. Recursively enumerable sets and degrees. Bull. Amer. Math. Soc. 84 (1978), no. 6, 1149--1181.
Research papers
| year=1954 | journal=Annals of Mathematics. Second SeriesAnnals of Mathematics
The Annals of Mathematics is a bimonthly mathematical journal published by Princeton University and the Institute for Advanced Study. It ranks amongst the most prestigious mathematics journals in the world by criteria such as impact factor.-History:The journal began as The Analyst in 1874 and was...
| issn=0003-486X | volume=59 | pages=379–407 | doi=10.2307/1969708 | issue=3 | jstor=1969708}}
| year=1998 | journal=Proc. London Math. Soc. (3) | issn=0024-6115 | volume=77 | pages=241–291 | doi=10.1112/S002461159800046X | issue=2}}
| year=1944 | journal=Bulletin of the American Mathematical Society
Bulletin of the American Mathematical Society
The Bulletin of the American Mathematical Society is a quarterly mathematical journal published by the American Mathematical Society...
| issn=0002-9904 | volume=50 | pages=284–316 | doi=10.1090/S0002-9904-1944-08111-1 | issue=5}}
| year=1999 | journal=Mathematical Research Letters | issn=1073-2780 | volume=6 | pages=711–722}}
| year=1977 | journal=Annals of Mathematics. Second Series
Annals of Mathematics
The Annals of Mathematics is a bimonthly mathematical journal published by Princeton University and the Institute for Advanced Study. It ranks amongst the most prestigious mathematics journals in the world by criteria such as impact factor.-History:The journal began as The Analyst in 1874 and was...
| issn=0003-486X | volume=105 | pages=121–139 | doi=10.2307/1971028 | issue=1 | jstor=1971028}}