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