- Semester
- 2025 Autumn Semester
- Location
- Peking University
- Classroom
- 二教 424
- Time
- Monday 13:00-15:00
Foundations of Computability Theory
Introduction
This course introduces the fundamental concepts, methods, and results of computability theory.
Contents and slides
- Lecture 1
- introduction, Turing machines, numbering, enumeration theorem, s-m-n theorem, recursion theorem
- Lecture 2
- c.e. sets, c.e. approximations, listing theorem, halting problem, $\mathsf{m}$-reducibility and $\mathsf{1}$-reducibility, index sets, Rice’s Theorem, hardness and completeness
- Lecture 3
- $\mathsf{m}$-degrees, $\mathsf{1}$-degrees, join, productive sets, creative sets, $\mathsf{1}$-completeness, Myhill isomorphism theorem
- Lecture 4
- oracle Turing machines, Turing reducibility, use principle, relativization, Turing degrees, Turing jump, Jump Theorem
- Lecture 5
- bounded Turing reducibilities, truth-table reducibilities, c.a. sets, $\omega$-c.e. and $n$-c.e. sets, Shoenfield limit lemma, low and high hierarchy
- Lecture 6
- arithmetical hierarchy, $\Sigma_n$-completeness, Post’s theorem, hierarchy theorem, classifying index sets
- Lecture 7
- relativized Post’s theorem, low theorem, high theorem, domination and escaping domination, Martin’s high domination theorem, computably dominated sets
- Lecture 8
- orthogonal lowness properties, trees, Weak König’s lemma, Cantor space, compactness, $\Sigma^0_1$ and $\Pi^0_1$ classes, low basis theorem, computably dominated basis theorem, cone avoidance basis theorem
- Lecture 9
- Post’s problem, simple sets, hypersimple sets, Dekker’s theorem
- Lecture 10
- permitting arguments, effective simple sets, diagonally non-computable degrees, fixed-point-free functions, Arslanov completeness criterion
- Lecture 11
- Kleene-Post theorem, generic sets, Friedberg completeness criterion, finite extension arguments, generic sets
- Lecture 12
- finite injury method, low simple sets, Friedberg-Muchnik theorem
- Lecture 13
- cone avoidance theorem, Sacks splitting theorem
- Lecture 14
- Peano arithmetic, Gödel’s first incompleteness theorem
- Lecture 15
- $\Sigma_1$-completeness of $\mathsf{PA}$, $\mathsf{DNC}_2$ functions, Gödel-Rosser’s incompleteness theorem, Gödel’s second incompleteness theorem, $\mathsf{PA}$ degrees
References
- Turing Computability: Theory and Applications, Robert I. Soare, Springer, 2016.
- Computability, Benoît Monin & Ludovic Patey, draft.