par Charles Corge

Ellipses, avril 2008
506 p. en 19 × 24, ISBN 978-2-7298-3772-3

En proposant en 1936 un modèle de machine élémentaire capable de mener tout calcul imaginable, Alain Turing a induit tous les développements des ordinateurs et de l’informatique de ces soixante dernières années.

Quarante ans plus tard, John H. Conway introduisait son « jeu de la vie » premier exemple d’automate cellulaire. Or un tel automate permet de modéliser l’évolution des configurations successives prises par le ruban d’une machine de Turing, mais aussi de simuler l’évolution de populations biologiques. Quiconque veut comprendre la notion moderne de calcul doit acquérir une maîtrise des deux concepts.

Le livre, préfacé par Jean-Paul Delahaye et précédé d’un avant propos de présentation et d’une biographie d’Alain M. Turing, comporte quatorze chapitres :

1. Symbolique paléolithique et machine de Turing.
2. Machine de Turing : généralités et utilitaires.
3. L’arithmétique des bâtons.
4. Calculabilité et récursivité primitive.
5. La fonction d’Ackermann.
6. Turing-calculabilité et récursivité non primitive.
7. Indécidabilité.
8. Vers les automates cellulaires.
9. Les automates cellulaires : caractérisation.
10. Voisinages de von Neumann.
11. Le voisinage de Moore.
12. Le voisinage de Margolus.
13. Le monde des fourmis.
14. Auto réplication et vie artificielle.

Chaque chapitre est divisé en paragraphes et sous-paragraphes et accompagné d’une abondante bibliographie, mais il n’y a pas d’index qui aurait facilité la recherche d’un auteur ou d’un concept dan un ouvrage aussi monumental.

Ouvrage de base pour information d’informaticien, ce livre intéressera les enseignants à plus d’un titre : histoire et préhistoire de l’algorithmique, relations entre logique, informatique et calcul, modèles d’évolution de populations, …

Les cinq derniers chapitres contiennent une étude très détaillée de nombreux exemples qui peuvent faire l’objet d’observations en classe, en TPE ou en club.

Une mine pour préparer l’épreuve orale de modélisation de l’agrégation. Un ouvrage de référence pour les CDI.