Weaker Reductions
According to the Church-Turing thesis, a Turing reduction is the most general form of an effectively calculable reduction. Nevertheless, weaker reductions are also considered. A set A is said to be arithmetical in B if A is definable by a formula of Peano arithmetic with B as a parameter. The set A is hyperarithmetical in B if there is a recursive ordinal α such that A is computable from, the α-iterated Turing jump of B. The notion of relative constructibility is an important reducibility notion in set theory.
Read more about this topic: Turing Reduction
Famous quotes containing the words weaker and/or reductions:
“But, when nothing subsists from a distant past, after the death of others, after the destruction of objects, only the senses of smell and taste, weaker but more enduring, more intangible, more persistent, more faithful, continue for a long time, like souls, to remember, to wait, to hope, on the ruins of all the rest, to bring without flinching, on their nearly impalpable droplet, the immense edifice of memory.”
—Marcel Proust (1871–1922)
“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)