Definition
Given two sets of natural numbers, we say is Turing reducible to and write
if there is an oracle machine that computes the characteristic function of A when run with oracle B. In this case, we also say A is B-recursive and B-computable.
If there is an oracle machine that, when run with oracle B, computes a partial function with domain A, then A is said to be B-recursively enumerable and B-computably enumerable.
We say is Turing equivalent to and write if both and The equivalence classes of Turing equivalent sets are called Turing degrees. The Turing degree of a set is written .
Given a set, a set is called Turing hard for if for all . If additionally then is called Turing complete for .
Read more about this topic: Turing Reduction
Famous quotes containing the word definition:
“... we all know the wag’s definition of a philanthropist: a man whose charity increases directly as the square of the distance.”
—George Eliot [Mary Ann (or Marian)
“I’m beginning to think that the proper definition of “Man” is “an animal that writes letters.””
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)
“The definition of good prose is proper words in their proper places; of good verse, the most proper words in their proper places. The propriety is in either case relative. The words in prose ought to express the intended meaning, and no more; if they attract attention to themselves, it is, in general, a fault.”
—Samuel Taylor Coleridge (1772–1834)