Turing degree


In computer science and mathematical logic the Turing degree (named after Alan Turing) 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 problems. The Turing degree of a set is a measure of how difficult it is to solve the decision problem associated with the set, that is, to determine whether an arbitrary number is in the given 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.

Turing equivalenceEdit

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 XT 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 XT 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:

  • XT X
  • XT Y implies YT X
  • If XT Y and YT Z then XT Z.

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 XT 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 XY, is defined to be the union of the sets {2n : nX} and {2m+1 : mY}. The Turing degree of XY 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 ab. 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 given their index as input) 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 XT Y. A key example is 0′, the degree of the halting problem.

Basic properties of the Turing degreesEdit

  • 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 countable. The set of degrees greater than a has size  .

Structure of the Turing degreesEdit

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 propertiesEdit

  • 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 order.
  • The Turing degrees are not linearly ordered by ≤T. [1]
  • In fact, 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 jumpEdit

  • For every degree a there is a degree strictly between a and a′. In fact, there is a countable family of pairwise incomparable degrees between a and a′.
  • Jump inversion: 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 ai+1ai for each i.
  • Post's theorem, establishing a close correspondence between the arithmetical hierarchy and finitely iterated Turing jumps of the empty set

Logical propertiesEdit

  • 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   with the language ⟨ ≤, = ⟩.

Recursively enumerable Turing degreesEdit

A finite lattice that can't be embedded in the r.e. degrees.

A degree is called recursively enumerable (r.e.) if it contains a recursively enumerable set. Every r.e. degree is below 0′, but not every degree below 0′ is r.e..

  • (G. E. Sacks, 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.
  • (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.
  • (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. Soare, 1980) Not all finite lattices can be embedded in the r.e. degrees (via an embedding that preserves suprema and infima). A particular example is shown to the right.
  • (L. A. Harrington and T. A. Slaman, 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 methodEdit

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 (Friedberg–Muchnik theorem). 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 a r.e. set X is to list a countable sequence of requirements that X must satisfy. For example, to construct a 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 be 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.

See alsoEdit


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
  • Odifreddi, P. G. (1989), Classical Recursion Theory, Studies in Logic and the Foundations of Mathematics, vol. 125, Amsterdam: North-Holland, ISBN 978-0-444-87295-1, MR 0982269
  • Odifreddi, P. G. (1999), Classical recursion theory. Vol. II, Studies in Logic and the Foundations of Mathematics, vol. 143, Amsterdam: North-Holland, ISBN 978-0-444-50205-6, MR 1718169
  • Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0-262-68052-1, ISBN 0-07-053522-1
  • Sacks, Gerald E. Degrees of Unsolvability (Annals of Mathematics Studies), Princeton University Press. ISBN 978-0-6910-7941-7
  • Simpson, S. Degrees of unsolvability: a survey of results. Handbook of Mathematical Logic, North-Holland, 1977, pp. 631–652.
  • Shoenfield, Joseph R. Degrees of Unsolvability, North-Holland/Elsevier, ISBN 978-0-7204-2061-6.
  • Shore, R. (1993). "The theories of the T, tt, and wtt r.e. degrees: undecidability and beyond". In Univ. Nac. del Sur, Bahía Blanca (ed.). Proceedings of the IX Latin American Symposium on Mathematical Logic, Part 1 (Bahía Blanca, 1992). Notas Lógica Mat. Vol. 38. pp. 61–70.
  • 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. MR508451
Research papers
  • Kleene, Stephen Cole; Post, Emil L. (1954), "The upper semi-lattice of degrees of recursive unsolvability", Annals of Mathematics, Second Series, 59 (3): 379–407, doi:10.2307/1969708, ISSN 0003-486X, JSTOR 1969708, MR 0061078
  • Lachlan, A.H. (1966a), "Lower Bounds for Pairs of Recursively Enumerable Degrees", Proceedings of the London Mathematical Society, 3 (1): 537–569, CiteSeerX, doi:10.1112/plms/s3-16.1.537.
  • Lachlan, A.H. (1966b), "The impossibility of finding relative complements for recursively enumerable degrees", J. Symb. Log., 31 (3): 434–454, doi:10.2307/2270459, JSTOR 2270459.
  • Lachlan, A.H.; Soare, R.I. (1980), "Not every finite lattice is embeddable in the recursively enumerable degrees", Advances in Mathematics, 37: 78–82, doi:10.1016/0001-8708(80)90027-4.
  • Nies, André; Shore, Richard A.; Slaman, Theodore A. (1998), "Interpretability and definability in the recursively enumerable degrees", Proceedings of the London Mathematical Society, 77 (2): 241–291, CiteSeerX, doi:10.1112/S002461159800046X, ISSN 0024-6115, MR 1635141
  • Post, Emil L. (1944), "Recursively enumerable sets of positive integers and their decision problems", Bulletin of the American Mathematical Society, 50 (5): 284–316, doi:10.1090/S0002-9904-1944-08111-1, ISSN 0002-9904, MR 0010514
  • Sacks, G.E. (1964), "The recursively enumerable degrees are dense", Annals of Mathematics, Second Series, 80 (2): 300–312, doi:10.2307/1970393, JSTOR 1970393.
  • Shore, Richard A.; Slaman, Theodore A. (1999), "Defining the Turing jump", Mathematical Research Letters, 6 (6): 711–722, doi:10.4310/mrl.1999.v6.n6.a10, ISSN 1073-2780, MR 1739227
  • Simpson, Stephen G. (1977), "First-order theory of the degrees of recursive unsolvability", Annals of Mathematics, Second Series, 105 (1): 121–139, doi:10.2307/1971028, ISSN 0003-486X, JSTOR 1971028, MR 0432435
  • Thomason, S.K. (1971), "Sublattices of the recursively enumerable degrees", Z. Math. Logik Grundlag. Math., 17: 273–280, doi:10.1002/malq.19710170131.
  • Yates, C.E.M. (1966), "A minimal pair of recursively enumerable degrees", Journal of Symbolic Logic, 31 (2): 159–168, doi:10.2307/2269807, JSTOR 2269807.
Inline citations
  1. ^ J. DeAntonio, The Turing degrees and their lack of linear order (2010), p.9. Accessed 4 January 2022.