Cet article place la machine de Turing au centre des questionnements mathématiques les plus fondamentaux (les 23 problèmes de Hilbert), mais en même temps il en propose plusieurs simulations (avec Scratch) pour asseoir la compréhension de son fonctionnement. La machine de Turing est une machine élémentaire. On considère souvent que c’est le modèle théorique d’un ordinateur (ce qui est partiellement vrai). Bien qu’élémentaire, cette machine est traversée par les problématiques fondamentales de l’informatique, et ces problématiques sont souvent exprimées en termes de machines de Turing.
Dans ce premier article, l’auteur présente cette machine et l’implémente et ce, en traitant les trois volets suivants :
1. Qu’est-ce qu’une machine de Turing ?
2. Machine de Turing et calculabilité
3. Machine de Turing et complexité