Reductions Weaker Than Turing Reducibility
Although Turing reducibility is the most general reducibility that is effective, weaker reducibility relations are commonly studied. These reducibilities are related to relative definability of sets over arithmetic or set theory. They include:
- Arithmetical reducibility: A set A is arithmetical in a set B if A is definable over the standard model of Peano arithmetic with an extra predicate for B. Equivalently, according to Post's theorem, A is arithmetical in B if and only if A is Turing reducible to, the nth Turing jump of B, for some natural number n. The arithmetical hierarchy gives a finer classification of arithmetical reducibility.
- Hyperarithmetical reducibility: A set A is hyperarithmetical in a set B if A is definable (see analytical hierarchy) over the standard model of Peano arithmetic with a predicate for B. Equivalently, A is hyperarithmetical in B if and only if A is Turing reducible to, the αth Turing jump of B, for some B-recursive ordinal α.
- Relative constructibility: A set A is relatively constructible from a set B if A is in L(B), the smallest transitive model of ZFC set theory containing B and all the ordinals.
Read more about this topic: Reduction (recursion Theory)
Famous quotes containing the words reductions and/or weaker:
“The work was like peeling an onion. The outer skin came off with difficulty ... but in no time you’d be down to its innards, tears streaming from your eyes as more and more beautiful reductions became possible.”
—Edward Blishen (b. 1920)
“Women have their heads in their hearts. Man seems to have been destined for a superior being; as things are, I think women generally better creatures than men. They have weaker appetites and weaker intellects but much stronger affections. A man with a bad heart has been sometimes saved by a strong head; but a corrupt woman is lost forever.”
—Samuel Taylor Coleridge (1772–1834)