Editing Turing reduction (section)

== 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. Set <math>A</math> is said to be '''[[arithmetical set|arithmetical]] in''' <math>B</math> if <math>A</math> is definable by a formula of [[Peano arithmetic]] with <math>B</math> as a parameter.  The set <math>A</math> is '''[[hyperarithmetical hierarchy|hyperarithmetical]] in''' <math>B</math>  if there is a [[recursive ordinal]] <math>\alpha</math> such that <math>A</math> is computable from <math>B^{(\alpha)}</math>, the ''α''-iterated Turing jump of <math>B</math>.  The notion of '''[[Constructible universe#Relative constructibility|relative constructibility]]''' is an important reducibility notion in [[set theory]].