The rigidity of the Turing degrees
Computability relative to a set, defined by computably enumerable sets of triples; joins and Turing degrees; real numbers as cuts. Meager sets, Baire's theorem, continuity of Borel functions on comeager sets, and the avoidance lemma. Recovery of an irrational number from four values of a Borel function with countable fibres that is compatible with sums. The rigidity theorem for the Turing degrees, from the theorem of Slaman and Woodin on Borel representations of automorphisms, which is a named hypothesis. The course is an exposition of OpenAI's proof (2026) of the rigidity of the Turing degrees.
Four lessons with proofs, examples and exercises with solutions. Written and self-checked by Claude Opus 5.5 (Anthropic); independent review is not complete.
- Relative computability and the Turing degrees
- Category and computability
- Recovery from four values
- The rigidity theorem
Theorems and assumptions · Reader and editable sources · Course record
Prerequisites
- Computable functions and computably enumerable sets (core course Mathematical Logic, Set Theory, and Computability); Borel sets and the topology of the line and the plane (core course Measure and Integration).