Assertion de la calculabilité des fonctions
1. Machines de Turing
2. Les limites du calcul
3. Universalité et complétude
4. Thèse de Church Turing
Identification des classes de fonctions calculables.
Automate
Pablo Arrighi, Gilles Dowek, 2011The physical Church-Turing thesis and the principles of quantum theory, p.1102.1612.
M. Pégny, 2012, Les deux formes de la thèse de Church-Turing et l’épistémologie du calcul, Philosophia Scientiae, 16(3), p.39–67.
Michael Sipser, 2006, Introduction to the theory of computation, Course Technology.
Turlough Neary & Damien Woods, 2007, The Complexity of Small Universal Turing Machines, pages 791–798.