CultureMATH. Algorithmes et puzzles : une ultime approche de Turing.

Résumé

Alan Turing (1912-1954) est, à juste titre, considéré comme le co-inventeur de l’ordinateur (avec J. von Neumann). La « machine de Turing universelle » est bien une préfiguration théorique du « calculateur programmable ». Dans ses travaux fondateurs de 1936, Turing se référaient directement à des questions de calculabilité (les nombres réels calculables) et de décidabilité (le problème de la décision, ou Entscheidungsproblem de Hilbert). Dans l’article de 1954, c’est en partant de considérations moins « confidentielles », destinées à un plus large public, qu’il présente une (petite) partie de la théorie de la calculabilité. Les « puzzles » (casse-têtes, énigmes, etc.) forment le point de départ de la discussion. Partant de ces « récréations mathématiques », Turing expose une nouvelle formalisation des algorithmes, dans l’esprit des travaux plus récents de Post et Markov.

Notes

Cet article est sous la rubrique « Thèmes ».

CultureMATH fait partie des Sites Ressources de la Direction de l’Enseignement Scolaire (DESCO) et des Ecoles Normales Supérieures.

Cet article est en libre accès sur le site CultureMATH

Pistes d’utilisation en classe

Parmi les « puzzles » étudiés dans le texte, une place importante est donnée au taquin. En suivant la démarche de Turing, on peut envisager un examen approfondi, et non moins ludique, de ce jeu, qui fournit une intéressante application de la théorie des groupes ; on peut même considérer des versions simplifiées (3×3 cases au lieu de 4×4), ou au contraire d’une plus grande complexité, dans une approche combinatoire (méthode de partition). Il peut également illustrer des questions d’algorithmique générale (par exemple les différentes manières d’explorer un arbre) et sensibiliser aux problèmes de la théorie élémentaire de la calculabilité (notion de procédure effective, de complexité algorithmique, etc.).

Données de publication

Éditeur CultureMATH – ENS Ulm Paris , 2009 Index Bibliogr.

Public visé élève ou étudiant, enseignant, tout public Niveau licence, lycée, terminale Âge 17, 18, 19, 20

Type monographie, polycopié Langue français Support internet