Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Turing degree
Summary
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 (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 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 reduction
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.