Une machine de Turing... avec des Lego
Les
documents disponibles sur cette page ainsi que le contenu de la page
sont mis à disposition selon les termes de la Licence Creative Commons Attribution - Partage dans les Mêmes Conditions 4.0 International 
Notions abordées :
Cette activité présente de manière ludique un modèle théorique inventé par Alan Turing et qui a la même puissance théorique qu'un ordinateur. Elle touche à l'algorithmique et à la programmation.
Public :
Cette activité nécessite et fait travailler la capacité d'abstraction. Elle demande de comprendre et s'adapter à un langage précis et assez rudimentaire, tout en continuant d'être créatif. Son côté ludique permet d'attirer les élèves de primaire mais cela risque d'être ardu avant la toute fin de primaire, et pour exploiter toutes les possibilités de l'activité mieux vaut attendre le collège/lycée.
Cette activité a été testée avec des collégiens de 4ème et 3ème, et avec des élèves de première scientifique
Matériel :
La liste précise se trouve dans la fiche complète téléchargeable dans la section Liens en bas de cette page. J'utilise (mais si vous trouvez d'autre solutions libre à vous) pour chaque groupe de 2 à 4 élèves :- des petites briques de Lego (taille 2 x 2) de différentes couleurs et en quantité,
- un support pour constructions Lego, taillé en bandes de 4 plots de large (2 c'est faisable mais plus fragile),
- de quoi écrire, pour stocker l'état de contrôle de la machine et écrire le programme de vos propres machines,
- un morceau de papier/carton taillé en flèche pour faire la tête de lecture,
- les exemples de machines donnés dans la fiche complète, imprimés ou reproduits.
Principe :
La machine de Turing se compose d'un ruban, sur lequel on peut écrire des lettres (pour nous c'est plutôt fixer des briques) équipé d'une tête de lecture (qui pointe à sur une des briques) ainsi que d'un espace pour stocker un état de contrôle. Le programme d'une machine du Turing va consister en une liste de règles. Par exemple une règle peut dire que si l'état de contrôle est "truc" et que la tête de lecture pointe sur une brique bleue, alors on reste dans l'état "truc", on remplace la brique bleue, et on déplace la tête de lecture d'une brique vers la gauche.
Et avec ces règles rudimentaires on peut faire pas mal de chose. L'activité consiste d'abord à observer des programmes tout faits et à comprendre ce qu'ils font, en manipulant les briques colorées, puis à se lancer des défis de programmation, afin de réaliser des machines variées.
On peut par exemple remplacer toutes les briques par des vertes, ou ajouter une brique jaune à la fin de notre "mot" sur le ruban, remplacer toutes les briques rouges par des vertes,... Et avec un peu d'imagination on peut même faire des choses plus compliquées, comme calculer par exemple.
Extensions :
Une fois que le principe est posé, la fiche complète ci-dessous propose une dizaine de défis, plus ou moins difficiles. Il peut être intéressant de demander aux participants de créer leurs propres défis de programmation (et pourquoi pas me les envoyer ;o) ).
Liens :
- Edit : 08/2018 : voici enfin la fiche complète contenant le contexte informatique, la description de l'activité et des exemples de machines de Turing à imprimer.
- La fiche d'explication distribuée aux lycéens qui ont testé l'activité pour la journée d'immersion. Elle est moins facile d'accès, bien moins complète et nécessite des explications préalables.
- Une vidéo a été tournée en janvier 2018, j'attends de recevoir la maquette.
Photos :
Le matériel tel que je l'utilise, un programme écrit par des collégiens, et encore le matériel.
