---

Bibliographie:

• P.Wolper, Introduction à la calculabilité, 2eme edition, Dunod
• J.Stern, Fondements mathématiques de l'informatique, Mc Graw Hill.
• P.Dehornoy, Mathématiques de l'informatique, Dunod.
• J.E.Hopcroft & J.D.Ullman. Introduction to automata theory, languages and computation.
• C.H. Papadimitriou. Computational complexity. Addison Wesley, 1994.

D'autres livres:

• Harry R. Lewis et Christos H. Papadimitriou, Elements of the theory of computation. Prentice-Hall, 1981.
• Michael Sipser, Introduction to the theory of computation. PWS Publishing Company, Boston, 1997
• R.Lassaigne et M.De Rougemont, Logique et complexité, Hermes.
• P.Dehornoy, Complexité et décidabilité, Springer 1993.
• A.Turing, La machine de Turing, Points Sciences (poche).
• A.Hodges, Alan Turing ou l'énigme de l'intelligence, Payot.

 

---

Cours disponibles sur le web:

• Olivier Biberstein et José Rolim, Eléments d'informatique théorique, Université de Genève.
• le cours d'Olivier Carton
• le cours de Pierre Wolper 
• le cours de Marie-Pierre Béal
• un cours de Calculabilité et Complexité de S. Cerrito, H. Comon, et C. Crepeau.  
• Pour aller plus loin: voir les notes de cours d'Oded Goldreich (en anglais)
  

---

Quelques sites intéressants:

• Un site consacré à Alan Turing
• quelques implémentations de machines de Turing en JavaScript
• L'article de Turing de 1936
• La page de l'Institut Clay sur le problème P vs NP
• Le "Complexity Zoo" de Scott Aaronson

---