チューリング還元
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 formula_1 is said to be arithmetical in formula_2 if formula_1 is definable by a formula of Peano arithmetic with formula_2 as a parameter. The set formula_1 is hyperarithmetical in formula_2 if there is a recursive ordinal formula_86 such that formula_1 is computable from formula_88, the α-iterated Turing jump of formula_2. The notion of relative constructibility is an important reducibility notion in set theory.