Machines de Turing et Automates cellulaires. Du trait gravé au très animé - Charles Corge - Ellipses - broché - Etude

À la question posée par David Hilbert en 1900, reprise par Max Newman, sous la forme : «Existe-t-il un procédé mécanique qui permette de savoir si une proposition mathématique est démontrable ou non ?», Alan Turing répondit en 1936 en inventant une machine abstraite qui porte son nom, d’une simplicité maximale, qui imprime ou lit des traits dans les cases alignées d’un ruban de papier sans fin. L’auteur propose de le suivre dans l’analyse très fine du fonctionnement de cette machine en décomposant les procédés de l’arithmétique élémentaire en ses mécanismes les plus fondamentaux jusqu’à la limite du possible. Il amène le lecteur petit à petit, en le prenant par la main, vers des calculs de plus en plus élaborés cernant, ce faisant la notion de fonctions effectivement calculables. Il montre dans le détail qu’une telle machine jouit de la propriété d’universalité : elle est capable d’exécuter tout calcul imaginable que l’homme peut spécifier à l’aide d’un algorithme, c’est-à-dire une sui