Turing Reducibility
摘要
Turing reducibility is introduced as a notion of relative complexity and we study the relationship between the arithmetic hierarchy and the jump operator. Several advanced constructions in computability are surveyed, including the construction of incomparable sets, minimal degrees, and an incomplete non-computable computably enumerable set.