Editing Computability theory (section)

===Generalizations of Turing computability===
Computability theory includes the study of generalized notions of this field such as [[arithmetic reducibility]], [[hyperarithmetical reducibility]] and [[alpha recursion theory|α-recursion theory]], as described by Sacks in 1990.<ref name="Sacks_1990"/> These generalized notions include reducibilities that cannot be executed by Turing machines but are nevertheless natural generalizations of Turing reducibility. These studies include approaches to investigate the [[analytical hierarchy]] which differs from the [[arithmetical hierarchy]] by permitting quantification over sets of natural numbers in addition to quantification over individual numbers. These areas are linked to the theories of well-orderings and trees; for example the set of all indices of computable (nonbinary) trees without infinite branches is complete for level <math>\Pi^1_1</math> of the analytical hierarchy. Both Turing reducibility and hyperarithmetical reducibility are important in the field of [[effective descriptive set theory]]. The even more general notion of [[degree of constructibility|degrees of constructibility]] is studied in [[set theory]].