Archive 2019
Program requirementsexamen
TeacherPaul Rozière et Hervé Fournier
Weekly hours 4 h CM , 2 h TD
Years Master Logique et Fondements de l'Informatique

Syllabus

  • Computability: recursive functions and functions computable by machines; logical characterization of computable functions; s-m-n theorem and fixed point theorems; the concept of reduction and undecidable problems.
  • Introduction to complexity: time and space complexity classes, hierarchy theorems, reductions, completeness, Boolean circuits, introduction to algebraic complexity.
  • Formal arithmetic: Peano axioms and weak subsystems; arithmetization of logic; undecidability theorems; Gödel's incompleteness theorems.

Bibliography

  • J.BARWISE (ed) : Handbook of Mathematical Logic (North-Holland, 1977-1999).
  • R.CORI & D.LASCAR : Logique mathématique : cours et exercices (Dunod, 2 tomes, 2003).
  • R.LASSAIGNE & M. de ROUGEMONT : Logique et Complexité (Hermès, 1996).
  • M. MACHTEY & P. YOUNG : An introduction to the General Theory of Algorithms (North Holland, 1978).
  • J.R. SCHOENFIELD : Mathematical Logic (Addison-Wesley, 1967. Assoc. for Symb. Logic, 2001).
  • R. SMULLYAN : Les Théorèmes d’Incomplétude de Gödel (Masson, 1993).
  • O. GOLDREICH : Computational Complexity : A Conceptual Perspective (Cambridge University Press, 2008).
  • N.D. JONES : Computability and Complexity : From a Programming Perspective (MIT Press, 1997).