12. Degrees of Unsolvability
Degrees of unsolvability study how undecidable problems can be compared according to their relative computational difficulty, rather than treating all undecidable problems as having the same level of complexity. The chapter begins with reducibility, where one problem is transformed into another in a computable way, so that a solution to the second problem would also give a solution to the first. Turing degrees are then introduced as equivalence classes of...