In
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
and
mathematical logic
Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...
the Turing degree (named after
Alan Turing
Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher and theoretical biologist. He was highly influential in the development of theoretical computer ...
) or degree of unsolvability of a set of
natural number
In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
s measures the level of algorithmic unsolvability of the set.
Overview
The concept of Turing degree is fundamental in
computability theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since ex ...
, where sets of natural numbers are often regarded as
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...
s. 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 (possibly 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 and many fundamental results were established by . 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
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric, and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. A simpler example is equ ...
, 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''.
A Turing degree is an
equivalence class
In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements ...
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
In mathematics, especially order theory, a partial order on a set is an arrangement such that, for certain pairs of elements, one precedes the other. The word ''partial'' is used to indicate that not every pair of elements needs to be comparable ...
≤ 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
In mathematics, the infimum (abbreviated inf; : infima) of a subset S of a partially ordered set P is the greatest element in P that is less than or equal to each element of S, if such an element exists. If the infimum of S exists, it is unique, ...
of the degrees of ''X'' and ''Y''. Thus
is a
join-semilattice
In mathematics, a join-semilattice (or upper semilattice) is a partially ordered set that has a join (a least upper bound) for any nonempty finite subset. Dually, a meet-semilattice (or lower semilattice) is a partially ordered set which has a ...
. 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 given their index as input) when using ''X'' as an oracle. The set ''X''′ is called the
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 ...
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
In computability theory (computer science), computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run for ...
.
Basic properties of the Turing degrees
* Every Turing degree is
countably infinite
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbe ...
, 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
In mathematics, a Set (mathematics), set is countable if either it is finite set, finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function fro ...
. 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 order
In mathematics, a partial order or total order < on a is said to be dense if, for all .
* The Turing degrees are not linearly ordered by ≤
T.
* 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.
* An infinite strictly increasing sequence a
1, a
2, ... of Turing degrees cannot have a least upper bound, but it always has an ''exact pair'' c, d such that ∀e (e<c∧e<d ⇔ ∃''i'' e≤a
''i''), and thus it has (non-unique) minimal upper bounds.
* Assuming the
axiom of constructibility
The axiom of constructibility is a possible axiom for set theory in mathematics that asserts that every set is constructible. The axiom is usually written as ''V'' = ''L''. The axiom, first investigated by Kurt Gödel, is inconsistent with the pr ...
, it can be shown there is a maximal chain of degrees of order type
.
Properties involving the jump
* 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 a
''i'' of degrees such that a′
''i''+1 ≤ a
''i'' for each ''i''.
*
Post's theorem
In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees.
Background
The statement of Post's theorem uses several concepts relating to definability and r ...
establishes a close correspondence between the
arithmetical hierarchy
In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy (after mathematicians Stephen Cole Kleene and Andrzej Mostowski) classifies certain sets based on the complexity of formulas that define th ...
and finitely iterated Turing jumps of the empty set.
Logical properties
* showed that the
first-order theory
In mathematical logic, a theory (also called a formal theory) is a set of sentences in a formal language. In most scenarios a deductive system is first understood from context, giving rise to a formal system that combines the language with deduct ...
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.
* showed that the jump operator is definable in the first-order structure of
with the language .
Recursively enumerable Turing degrees

A degree is called ''recursively enumerable'' (r.e.) or ''computably enumerable'' (c.e.) if it contains a
recursively enumerable set
In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if:
*There is an algorithm such that the ...
. Every r.e. degree is below 0′, but not every degree below 0′ is r.e.. However, a set
is many-one reducible to 0′ iff
is r.e..
* : The r.e. degrees are dense; between any two r.e. degrees there is a third r.e. degree.
* and : There are two r.e. degrees with no greatest lower bound in the r.e. degrees.
* and : There is a pair of nonzero r.e. degrees whose greatest lower bound is 0.
* : 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''.
* : Every finite
distributive lattice
In mathematics, a distributive lattice is a lattice (order), lattice in which the operations of join and meet distributivity, distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice o ...
can be embedded into the r.e. degrees. In fact, the countable
atomless Boolean algebra
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variable (mathematics), variables are the truth values ''true'' and ''false'', usually denot ...
can be embedded in a manner that preserves
suprema and infima.
* : 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 ): 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.
Additionally, there is Shoenfield's limit lemma, a set A satisfies
iff there is a "recursive approximation" to its characteristic function: a function ''g'' such that for sufficiently large ''s'',
.
A set ''A'' is called ''n''-r e. if there is a family of functions
such that:
* ''A''
s is a recursive approximation of ''A'': for some ''t'', for any ''s''≥''t'' we have ''A''
''s''(''x'') = ''A''(''x''), in particular conflating ''A'' with its characteristic function. ''(Removing this condition yields a definition of'' A ''being'' "weakly ''n''-r.e."'')''
* ''A''
s is an "''n''-trial predicate": for all ''x'', ''A''
0(''x'')=0 and the cardinality of
is ≤n.
Properties of ''n''-r.e. degrees:
* The class of sets of ''n''-r.e. degree is a strict subclass of the class of sets of (''n''+1)-r.e. degree.
* For all ''n''>1 there are two (''n''+1)-r.e. degrees a, b with
, such that the segment
contains no ''n''-r.e. degrees.
*
and
are (''n''+1)-r.e. iff both sets are weakly-''n''-r.e.
Post's problem and the priority method
Emil Post
Emil Leon Post (; February 11, 1897 – April 21, 1954) was an American mathematician and logician. He is best known for his work in the field that eventually became known as computability theory.
Life
Post was born in Augustów, Suwałki Govern ...
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 ''A
e'' and ''B
e'' for each natural number ''e'', where ''A
e'' requires that the oracle machine with index ''e'' does not compute 0′ from ''X'' and ''B
e'' 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 (if not injured) 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.
For example, a
simple
Simple or SIMPLE may refer to:
*Simplicity, the state or quality of being simple
Arts and entertainment
* ''Simple'' (album), by Andy Yorke, 2008, and its title track
* "Simple" (Florida Georgia Line song), 2018
* "Simple", a song by John ...
(and hence noncomputable r.e.)
low
Low or LOW or lows, may refer to:
People
* Low (surname), listing people surnamed Low
Places
* Low, Quebec, Canada
* Low, Utah, United States
* Lo Wu station (MTR code LOW), Hong Kong; a rail station
* Salzburg Airport (ICAO airport code: LO ...
''X'' (low means ''X''′=0′) can be constructed in infinitely many stages as follows. At the start of stage ''n'', let ''T''
''n'' be the output (binary) tape, identified with the set of cell indices where we placed 1 so far (so ''X''=∪
''n'' ''T''
''n''; ''T''
0=∅); and let ''P''
''n''(''m'') be the priority for not outputting 1 at location ''m''; ''P''
0(''m'')=∞. At stage ''n'', if possible (otherwise do nothing in the stage), pick the least ''i''<''n'' such that ∀''m'' ''P''
''n''(''m'')≠''i'' and Turing machine ''i'' halts in <''n'' steps on some input ''S''⊇''T''
''n'' with ∀''m''∈''S''\''T''
''n'' ''P''
''n''(''m'')≥''i''. Choose any such (finite) ''S'', set ''T''
''n''+1=''S'', and for every cell ''m'' visited by machine ''i'' on ''S'', set ''P''
''n''+1(''m'') = min(''i'', ''P''
''n''(''m'')), and set all priorities >''i'' to ∞, and then set one priority ∞ cell (any will do) not in ''S'' to priority ''i''. Essentially, we make machine ''i'' halt if we can do so without upsetting priorities <''i'', and then set priorities to prevent machines >''i'' from disrupting the halt; all priorities are eventually constant.
To see that ''X'' is low, machine ''i'' halts on ''X'' iff it halts in <''n'' steps on some ''T''
''n'' such that machines <''i'' that halt on ''X'' do so <''n''-''i'' steps (by recursion, this is uniformly computable from 0′). ''X'' is noncomputable since otherwise a Turing machine could halt on ''Y'' iff ''Y''\''X'' is nonempty, contradicting the construction since ''X'' excludes some priority ''i'' cells for arbitrarily large ''i''; and ''X'' is simple because for each ''i'' the number of priority ''i'' cells is finite.
See also
*
Martin measure
References
Monographs (undergraduate level)
*
*;
Monographs and survey articles (graduate level)
*
*
*
*
*
*
*
*
*
*
*
*
Research papers
*
*
*
*
*
*
*
*
*
*
*
*
*
Notes
{{Alan Turing
Computability theory
Theory of computation
Alan Turing