Computability theory and applications

The aim of this course is to give a solid background on computability theory, by covering the basic notions (Church-Turing thesis, Turing degrees, Pi^0_1 classes, the arithmetic hierarchy, hyperimmunity, finite extension method and priority constructions) but also more advanced topics.

Prerequisites

No specific prerequisite is necessary, except some mathematical maturity. It is helpful to have some basic notions of set theory, in particular Cantor's diagonal argument, or some basic knowledge of first order logic.

Grading

50% continuous control and 50% final exam. There will be weakly graded homework. The continuous control will be the average of the three best grades.

Lecture notes

The lectures will be based on the first chapters of following book:

  1. Monin, Patey. Calculabilité: Degrés turing/Théorie algorithmique de l'aléatoire/Mathématiques à rebours/Hypercalculabilité. pdf
  2. Monin, Patey. Computability Theory: Turing degrees/Algorithmic Randomness/Reverse Mathematics/Higher Computability Theory. pdf

Lectures

  1. Lecture 1: 20/11/2023. Models of computation and their advantages. The proper use of the Church-Turing thesis. Basic notions: computable function, existence of a universal program, SMN theorem, padding lemma, Kleene's recursion theorem, existence of non-computable sets. Computably enumerable sets, various characterisations. C.e. approximations. Relative computation, Turing reduction, Turing degrees, effective join.
  2. Lecture 2: 22/11/2023. Oracle machines, Turing functionals. Relativization. Use property. Turing jump. Limit-computable functions, Delta2 approximations. Modulus, computation function.
  3. Lecture 3: 27/11/2023. Finite extension method. Low and high degrees.
  4. Lecture 4: 29/11/2023. Arithmetic hierarchy. Many-one reduction. Post theorem. Rice theorem.
  5. Lecture 5: 04/12/2023. Konig's lemma. Computable and co-c.e. trees. Extendible node. Isolated path. Cantor space : open, closed classes. Compactness, continuity.
  6. Lecture 6: 06/12/2023. Effectively open and closed sets. Sigma01 and Pi01 classes. Low, computably dominated and cone avoidance basis theorems.
  7. Lecture 7: 11/12/2023. Borel hierarchy, effective hierarchy, difference between hierarchies on sets and classes. Basic introduction to forcing: generalization of the finite extension method.
  8. Lecture 8: 13/12/2023. PA degres, DNC2 degrees, universal instance. Finitely branching trees.
  9. Lecture 9: 18/12/2023. Equivalence finitely branching trees and Delta2 binary trees. Immunity, hyperimmunity. Hyperimmune functions. Weakly 1-generic functions.
  10. Lecture 10: 20/12/2023. Dominating function. Martin's domination theorem. Sub-uniform degrees. DNC functions, FPF functions.
  11. Lecture 11: 08/01/2024. Effectively immune sets, equivalence with DNC functions. DNC or High degrees. 1-generic degrees. Delta2 1-generics are low. No 1-generic computes a DNC function.
  12. Lecture 12: 10/01/2024. Characterization of 1-generic degrees as mutually hyperimumune functions. Friedberg-jump inversion. Posner-Robinson theorem.
  13. Lecture 13: 15/01/2024. Finite injury priority arguments. Existence of Turing incomparable c.e. sets. Existence of low c.e. sets.
  14. Lecture 14: 17/01/2024. Practice of the exam. Minimal degrees (optional).
  15. Lecture 15: 22/01/2024. Final exam.
  16. Lecture 16: 24/01/2024. Correction of the final exam.

Graded Exercises

Don't be discouraged by the exercises. I will adapt the grading depending on how the class succeeds.

  1. Week 1: Questions. Solutions
  2. Week 2: Questions. Solutions
  3. Week 3: Questions. Solutions
  4. Week 4: Questions. Solutions
  5. Week 5: Questions. Solutions
  6. Week 6: Questions. Solutions

Final exam

The final exam will be on 24/01/2024. It will last 2 hours. You are allowed to bring with you hand-written one-sided A4 page with your notes. Do not worry if the exam is long, or seems too complicated: the grading will be adapted to the overall success of the class.

  1. Previous final exam (it was way too long). Solutions

Contact

Email: ludovic.patey@computability.fr