12.5 Structure of Degrees
Global properties of the Turing degrees including incomparability, density, and jump structure.
4 notes
Global properties of the Turing degrees including incomparability, density, and jump structure.
Existence of intermediate degrees between computable sets and the halting problem.
Equivalence classes of sets under Turing reducibility and the ordering of computational power.
Reducibility, Turing degrees, recursively enumerable sets, Post's problem, and the structure of degrees.