Résumé de section

    • Bibliographie

      • M. Sipser. Introduction to the Theory of Computation. Second Edition. 2006 (proche du cours, en anglais)
      • O. Carton. Langages formels, calculabilité et complexité. 2008 (proche du cours, en français)
      • S. Perifel. Introduction à la calculabilité et à la complexité. Polycopié de cours de M1 informatique, Université Paris Diderot.
      • S. Perifel. Complexité algorithmique. Ellipse, 2014.
      • P. Odifreddi. Classical recursion theory. 1992 (pour aller beaucoup plus loin en calculabilité)
      • H. Rogers. Theory of recursive functions and effective computability. 1967
      • M. Davis. The Universal Computer: The Road from Leibniz to Turing. 2000
      • C. Moore et S. Mertens. The Nature of Computation. 2011
      • N. Jones. Computability and Complexity. 1997
      • S. Arora et B. Barak. Computational Complexity: A Modern Approach. 2009 (pour aller beaucoup plus loin en complexité)
      • C. Papadimitriou. Computational Complexity. 1993
      • L. Hemaspaandra et M. Ogihara. The Complexity Theory Companion. 2002
      • M. Garey et D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. 1979

    • Liens

    • RUBENS : une machine de Turing intégralement mécanique en Lego URL
    • Vidéos de réalisations concrètes de machines de Turing Page
    • Alan Turing : du calculable à l’indécidable, par Jean-Gabriel Ganascia URL
    • Des calculateurs universels, par Jean-Louis Giavitto URL
    • L'héritage d'Alan Turing URL