degree of unsolvability a maximal set of equally complex sets of natural numbers, with comparative complexity of sets of natural numbers construed as recursion-theoretic reducibility ordering. Recursion theorists investigate various notions of reducibility between sets of natural numbers, i.e., various ways of filling in the following schematic definition. For sets A and B of natural numbers: A is reducible to B iff (if and only if) there is an algorithm whereby each membership question about A (e.g., ’17 1 A?’) could be answered allowing consultation of an ‘oracle’ that would correctly answer each membership question about B. This does not presuppose that there is a ‘real’ oracle for B; the motivating idea is counterfactual: A is reducible to B iff: if membership questions about B were decidable then membership questions about A would also be decidable. On the other hand, the mathematical definitions of notions of reducibility involve no subjunctive conditionals or other intensional constructions. The notion of reducibility is determined by constraints on how the algorithm could use the oracle. Imposing no constraints yields T-reducibility (‘T’ for Turing), the most important and most studied notion of reducibility.
Fixing a notion r of reducibility: A is r-equivalent to B iff A is r-reducible to B and B is rreducible to A. If r-reducibility is transitive, r-equivalence is an equivalence relation on the class of sets of natural numbers, one reflecting a notion of equal complexity for sets of natural numbers. A degree of unsolvability relative to r (an r-degree) is an equivalence class under that equivalence relation, i.e., a maximal class of sets of natural numbers any two members of which are r-equivalent, i.e., a maximal class of equally complex (in the sense of r-reducibility) sets of natural numbers. The r-reducibility-ordering of sets of natural numbers transfers to the rdegrees: for d and dH r-degrees, let d m, dH iff for some A 1 d and B 1 dH A is r-reducible to B. The study of r-degrees is the study of them under this ordering.
The degrees generated by T-reducibility are the Turing degrees. Without qualification, ‘degree of unsolvability’ means ‘Turing degree’. The least T- degree is the set of all recursive (i.e., using Church’s thesis, solvable) sets of natural numbers. So the phrase ‘degree of unsolvability’ is slightly misleading: the least such degree is ‘solvability.’
By effectively coding functions from natural numbers to natural numbers as sets of natural numbers, we may think of such a function as belonging to a degree: that of its coding set.
Recursion theorists have extended the notions of reducibility and degree of unsolvability to other domains, e.g. transfinite ordinals and higher types taken over the natural numbers.
See also CHURCH’S THESIS, PHILOSOPHY OF MATHEMATICS , RECURSIVE FUNCTION THE – ORY. H.T.H.