Les machines de Post et à registres

calculer en semant des graines
mardi 2 novembre 2021
par  Alain BUSSER

image/svg+xml

Emil Post

Leon Emil Post, ayant perdu l’usage de sa main durant une partie de football dans les rues de New York, a été handicapé dans ses recherches par une psychose maniaco-dépressive qui lui a valu de nombreux séjours en hôpital [1]. Selon ses propres dires, il aurait inventé la machine de Turing en 1921 (donc 15 ans avant Turing) mais sa femme ayant jeté ses brouillons durant un de ses séjours à l’hôpital, il n’a pu prouver ce fait. Ses problèmes de santé l’ont également empêché de publier la description de sa machine. C’est en 1936, juste avant la parution de l’article de Turing, que Post, sur conseil de son ami Church, a rapidement rédigé finite combinatory processes dans lequel apparaît la description de sa machine. Celle-ci, contrairement à celle de Turing, est binaire.

Frances Allen

Dans les années 1950, Wang Hao (logicien) a effectué sur les machines de Turing (non nécessairement binaires) la même transformation qu’avait anticipée Post, à savoir représenter le graphe des états de la machine de Turing-Post-Wang par une liste d’instructions-états [2]. Au début des années 1960, Frances Allen propose en quelque sorte l’opération inverse, à savoir représenter le programme non pas par une suite d’instructions numérotées par un numéro de ligne, mais par un graphe, dit graphe de flot de contrôle.

D’où l’idée d’expérimenter des activités débranchées modélisant la machine de Post, afin de rendre un hommage conjoint à Post (qui a inventé sa machine en 1921) et Allen (dont l’annonce du décès a été faite 100 ans plus tard).

V.A.Uspensky

Des graphes de flot de contrôle pour la machine de Post existent déjà, ce sont les cas particuliers de machines de Turing où le codage est binaire, mais elles n’ont pas encore fait l’objet d’expérimentations en classe. À une exception possible près :

V.A.Uspensky a expérimenté les machines de Post à l’école primaire dans les années 1970. On voit un graphe de flot de contrôle à la page 42 de son livret. Uspensky part d’un programme (d’addition) sur la machine de Post :


puis il défait le tri topologique en dessinant le graphe de flot de contrôle :

Enfin, comme Frances Allen, il regroupe des instructions en blocs (sous-graphes) :

Ce qui lui permet d’analyser le programme et comprendre ce qu’il fait. Le découpage en blocs d’instructions est typique de ce que Turing appelait subroutines et ce passage est très rapidement perceptible lors de l’apprentissage : il permet pour l’enfant d’aller plus vite, une fois conceptualisé le bloc. Par exemple

finit par devenir la macro (ou bloc d’instructions)

puis

Chacun de ces paliers d’apprentissage apparaît à un stade différent selon les élèves, et en général après un certain temps consacré à manipuler la machine de Post [3].

Une machine de Post sans programme est manipulable en ligne ici. D’autres sont .

Le codage suivant a été choisi :

Symbole Uspensky Post explication
✔️ V marking the box he is in faire en sorte que l’index montre une graine
ξ erasing the mark in the box he is in faire en sorte que l’index montre une case vide
moving to the box on his right déplacer l’index vers la case à droite
moving to the box on his left déplacer l’index vers la case à gauche
👁️  ? determining whether the box he is in, is marked regarder si l’index montre une graine ou une case vide et déplacer le pion en conséquence

Matériel nécessaire

Post évoque des chambres ou boîtes alignées, que l’on peut aisément modéliser par des moitiés de bacs à glaçons comme ceux que l’on voit dans le premier onglet sowing de cet article. Qu’une case soit vide ou pleine, se voit à l’absence ou la présence d’une graine dedans. Et pour voir quelle case est en cours de traitement, on peut utiliser un objet ayant grossièrement la forme d’une pointe, par exemple cet objet, imprimé en 3D pour l’occasion :

dessin source au format Blender3D fichier pour imprimante 3D

Si on ne dispose pas d’une imprimante 3D, on peut coller sur la moitié d’un bouchon de liège, un dessin représentant une main ☝️ dont l’index est vers le haut. Il faut que les élèves puissent déplacer l’index de manière qu’il pointe vers la case de gauche ou celle de droite, si le programme le demande. Cela nécessite que le centre de gravité de l’ensemble cylindre+main soit assez bas pour garantir une bonne stabilité de l’ensemble. Il faut également que l’index soit assez bas pour éviter les erreurs de parallaxe, mais assez haut pour qu’il puisse montrer la case et ne pas être caché par elle.

Il faut également des objets (noyaux de litchi par exemple) suffisamment gros pour éviter d’en mettre plusieurs dans la même case. Et des feuilles imprimées donnant les programmes de la machine de Post, ainsi qu’un pion à poser (et déplacer) sur le graphe. Voici des exemples :

explications sur la machine de Post Exemples de programmes Programmes à imprimer

Il faut 3 élèves pour exécuter un programme :

  • l’un se charge de déplacer le pion sur le graphe, et dire aux deux autres ce que le pion dit de faire,
  • un autre est chargé de l’index et de ses déplacements,
  • le troisième est chargé des graines dans les cases (transport de graines entre les cases et la réserve de graines), et notamment dira au premier élève s’il y a une graine dans la case, ou non.

Par exemple, le pion étant posé sur un œil, le gestionnaire du graphe demande si l’index montre une graine. C’est le cas :

donc le pion part vers la droite du graphe (marquée par le smiley) :

L’exemple ci-dessus est en fait un castor affairé :

Graphe de flot de contrôle

On remarque que le castor affairé ci-dessus, démarré sur des cases vides, parcourt tout le graphe lors de l’exécution de son programme. La théorie de Frances Allen amène à conseiller que pour un jeu de tests donné

  • tous les sommets du graphe soient parcourus, au moins une fois, par le pion
  • tous les arcs du graphe soient parcourus, au moins une fois, par le pion.

L’activité permet donc, sans l’annoncer, de sensibiliser à la science du débogage.

Solitaire en dimension 1

L’un des programmes de la machine de Post proposés ci-dessus effectue un mouvement du jeu de solitaire en dimension 1 :

Il s’agit de faire sauter un pion par-dessus son voisin de droite, après avoir vérifié qu’il y avait bien de la place après. Sauter vers la gauche est également réalisable avec une machine de Post :

Les registres de Post peuvent donc être également utilisés pour jouer au solitaire en dimension 1. Ce jeu a fait l’objet d’un sujet de concours : la deuxième partie du sujet Mines-Pont 2021.

Dans le cas d’un solitaire à 8 bits, on peut construire, en remontant depuis la version finale où il ne reste plus qu’une graine, le graphe du jeu :

On constate que la graine que l’on doit retirer du jeu avant de prendre les pions en sautant par-dessus, ne doit pas être choisie n’importe où si on veut gagner. On voit par exemple que 110101 est une position gagnante ainsi que 1101 (obtenu en sautant vers la droite) mais jouer ensuite 10001 (en sautant vers la gauche) comme dans le sujet Mines-Ponts ne permet pas de gagner : on voit sur le graphe que sauter vers la droite pour aboutir à 11 est ce qu’il faut faire pour gagner.

Erreurs constatées

  • Le fait que les flèches vers la gauche et vers la droite indiquant dans quel sens décaler l’index (d’une seule case) ont la même forme que l’index, incite les plus jeunes à tourner l’index pour qu’il ressemble plus à la forme dessinée, au lieu de décaler l’index.
  • Décaler l’index d’une seule case est parfois difficile.
  • En plaçant plusieurs rangées de cases pour avoir une rangée plus longue, on n’évite pas forcément le blocage une fois arrivé au bout d’une rangée (la jonction avec la rangée suivante est parfois mal perçue).
  • Lorsqu’on regarde l’index en biais, il arrive parfois qu’une erreur de parallaxe attire l’attention sur la case voisine de celle pointée par l’index.
  • Le pion cache l’instruction à exécuter. En le soulevant il arrive qu’on ne se rappelle plus où le remettre après.
  • L’interprétation des cases vides ou pleines par un frowney ou un smiley est un peu abstraite.
  • Le fait que sur les dessins des mains, le pouce est écarté de l’index, suggère que les mains montrent le nombre 2 [4]. Il en est de même pour le signe √ utilisé pour représenter une case cochée.
  • Si les graines sont trop petites, on peut avoir tendance à ajouter une graine sans limite, surtout si l’instruction est de mettre une graine dans une case déjà pleine.

Cette dernière erreur suggère une variation sur le thème :

Machines à registres

Avec des graines plus petites, on peut mettre plusieurs graines dans une même case qui devient alors un registre [5]. Le nouveau modèle permet alors, en plus des compétences liées aux machines de Post, de mettre en œuvre celles liées à la numération [6]. Le codage change par rapport aux machines de Post [7] :

Version Post Version registres Signification
✔️ + ajouter une graine dans la case pointée par l’index
- enlever (si possible) une graine de la case pointée par l’index
déplacer l’index vers la case à droite
déplacer l’index vers la case à gauche
👁️  ? regarder s’il y a au moins une graine dans la case pointée par l’index

La lettre H (initiale de « halt ») a été choisie pour désigner l’arrêt du programme.

Voici le nouveau mode d’emploi :

Voici un programme d’addition :

En effet tant qu’il y a une graine dans la case de gauche, il la transfère dans la case de droite. Le nombre total de graines étant invariant, les nombres de graines ont été additionnés. Par exemple si au départ il y avait 3 graines dans la case de gauche (sur laquelle pointe l’index) et 5 graines dans la case de droite, lorsque la case de gauche est vide, celle de droite contient 8 graines.

Cette activité sensibilise donc au fait que l’addition est liée à un regroupement d’objets, et au comptage (pour vérifier qu’il y a 8 graines à l’arrivée, il faut bien les compter !).

Voici un programme de soustraction :

En effet s’il y a 3 graines dans la case de gauche (sur laquelle pointe initialement l’index) et 5 graines dans la case suivante, celle-ci contient à la fin 2 graines (différence entre 5 et 3).

Là encore, outre le comptage de graines nécessaire pour connaître le résultat de la soustraction, cette activité donne un sens à cette opération, par un invariant : la différence entre deux nombres est la même que celle entre leurs prédécesseurs [8]. On ramène alors la soustraction 5-3 aux soustractions plus simples

  • 4-2
  • 3-1
  • 2-0

Celle-ci étant terminée puisqu’il n’y a plus rien à soustraire [9].

Le programme ci-dessous divise par 2 le contenu de la première case (à la fin le nombre de graines de la seconde case est la moitié de celui qui était initialement dans la première case) :

On constate que chaque fois qu’on a ajouté une graine dans la seconde case, on en a enlevé 2 de la première case, ce qui revient au même que compter des constellations de 2 pour connaître le quotient par 2.

Et voici un programme de multiplication (il utilise 4 cases, et à la fin la 4e case contient le produit des nombres de graines qui étaient dans les deux cases de gauche) :

Cet algorithme, plus complexe que les précédents, permet de voir les phases d’abstraction décrites dans la partie sur Uspenky : Comme le faisait Frances Allen, certaines instructions ont été regroupées en blocs d’instructions qui ont le même effet qu’une seule instruction, mais plus complexe. Les trois blocs en bas ont les significations suivantes, de gauche à droite :

déplacer l’index de 2 cases vers la gauche transférer les graines de la case 3 vers la case 2 créer une copie des graines de la case 2 dans la case 3 et transférer les graines de la case 2 vers la case 4

Arrivé à ce niveau d’abstraction (ce qui devrait arriver automatiquement à force de pratiquer ce jeu), l’algorithme devient (la case 1 est un compteur indiquant combien de fois il faut faire ce qui est ci-dessous) :

  • enlever une graine de la case 1 (en haut à droite) pour ne pas refaire un travail déjà effectué
  • ajouter autant de graines qu’il y en a dans la case 2 à la case 4 et transférer les graines de la case 2 dans la case 3 (bloc de longueur 7 à droite),
  • retransférer les graines de la case 3 dans la case 2 (bloc de longueur 4 au milieu)
  • revenir à la case 1 (bloc de longueur 2 à gauche) et recommencer.

Puis, pour éviter de faire des choses trop répétitives, le niveau d’abstraction peut encore monter d’un cran et on arrive à

  • autant de fois qu’il y avait initialement de graines dans la case 1,
  • rajouter dans la case 4 autant de graines qu’il y en a dans la case 2.

Par exemple, s’il y avait initialement 3 graines dans la case 1 et 4 graines dans la case 2, le nombre final de graines dans la case 4 est 4+4+4=3×4. Alors que s’il y avait initialement 4 graines dans la case 1 et 3 graines dans la case 2, le nombre final de graines dans la case 4 est 3+3+3+3=4×3.

Le programme ci-dessous effectue une division euclidienne :

Initialement, le dividende est dans la case de gauche et le diviseur dans la seconde case en partant de la gauche. Les autres cases sont initialement vides. Le doigt montre initialement le diviseur. À la fin de l’exécution du programme, la troisième case contient le reste et la quatrième case contient le quotient.

Enfin, pour les courageux, ce programme calcule le pgcd des nombres de graines initialement présentes dans les deux premières cases :

P’’

Les graphes de flot de contrôle utilisés avec la machine à registre sont écrits dans un langage de programmation dérivé de P’’ ( « P double prime » ). Outre le + (incrémentation de la case pointée) et le - (décrémentation de la case pointée), il possède les caractères > (incrémentation du pointeur) et < (décrémentation du pointeur) ainsi que les parenthèses. On peut le tester en ligne en cliquant ci-dessous :

Attention : refermer une parenthèse correspondant à une parenthèse ouvrante non suivie d’un « - » (soustraction) peut faire planter le navigateur.

De même, le jeu Enigma possède un interpréteur similaire :

On peut également tester cet outil en ligne.

Autres jeux inspirés par Post

Post était surtout spécialiste de la théorie algébrique des langages (règles de réécriture). Certains de ses travaux peuvent donc donner lieu à des jeux intéressants pour des élèves en cours d’acquisition du langage écrit :

  • Le jeu du caviar est basé sur le comptage et la reconnaissance de motifs. On peut y jouer avec des perles : les perles qu’on ajoute à droite du collier forment un motif qui dépend de la couleur de la perle de gauche puis on enlève les 2 perles les plus à gauche et on recommence. Ce jeu est praticable dès l’école maternelle mais requiert une attention soutenue pendant longtemps.
  • Le problème de correspondance de Post est un jeu où on pose des cartes (ou des dominos) de telle manière que le mot du dessus soit le même que le mot du dessous. En voici quelques exemples jouables en ligne (la plupart sont dans un alphabet de deux lettres) :
l’original (Post 1946) alphabet ternaire 4 cartes suffisent un jeu de Jeff Erickson un jeu difficile (Erickson)

Fête de la science

Les machines de Post et à registres ont été testées durant la fête de la science 2021 avec la caravane de l’IREMI.

lycée Rontaunay

La première date a été le lycée Rontaunay. Les graines utilisées sont en caoutchouc qui supporte bien le gel hydroalcoolique :

Les élèves trouvent un moyen à la fois esthétique et ergonomique pour stocker les graines de la réserve de graine :

L’animation des jeux a été assurée par des élèves du lycée, qui ont suivi une rapide formation en début de matinée puis ont initié leurs camarades aux machines de Post.

Voici un programme en cours d’exécution, on voit le déplacement de l’index vers une case occupée, puis une hésitation (l’instruction est de placer une graine alors qu’il y en a déjà une) puis un nouveau déplacement de l’index :

Un castor affairé s’apprête à construire un motif grâce à ce programme :

Un élève vient de poser l’addition 3+3 (3 graines de chaque côté de la case vide) et s’apprête à lancer le programme d’addition sur la machine de Post :

Les machines à registre semblent avoir eu la préférence des élèves animateurs de l’activité. Celle-ci a fait l’objet d’un rappel sur les fonctions :

En effet, il n’y a de graines que dans la première case avant le début du calcul, et que dans la seconde case à la fin du calcul. Le nombre final de graines est donc fonction du nombre initial de graines. Le but du jeu, dans ce cas, était d’essayer de deviner quelle est la fonction. L’exécution répétée du programme permet de construire le tableau de valeurs suivant :

nombre initial de graines nombre final de graines
0 0
1 0
2 1
3 1
4 2
5 2
6 3

Iris Hoarau

À l’école Iris Hoarau, la plupart des élèves ayant semé des graines avec la machine de Post (en fait, à registres) étaient en CE2. Mais une classe de CM1 est passée et elle a eu droit à la version binaire.

binaire

En CM1 comme en CE2, les équipes étaient idéalement formées de 3 personnes, l’une pour bouger le pion (« Monsieur Post »), une autre pour bouger le doigt et une troisième pour effectuer les semis :

Des élèves viennent de finir (on le voit au fait que Monsieur Post arrive sur un panneau stop) le calcul 4+2 :

L’opération 4-2 est en cours de calcul ici :

En fait la soustraction 4-2 a été transformée en 3-1 qui donne le même résultat.

Et ici c’est l’opération 5-1 qui est en cours de calcul :

L’opération 5-1 a été transformée en 4-0 ce qui fait que le calcul est bientôt terminé :

On voit ici une erreur de calcul :

En effet, là où se trouve Monsieur Post, l’exécution du programme devait mener la main à un mouvement vers la gauche (la droite sur la photo) :

Les élèves de CE2 ont eu droit à des manipulations sur machines à registres.

Travail en équipe

Typiquement il y a trois élèves par équipe :

  • l’un s’occupe des mouvements du pion,
  • un autre gère le doigt
  • un (ou deux) autre sème les graines :

Parfois les mouvements des membres de l’équipe sont simultanés :

On verbalise beaucoup avec cette activité :

Parfois il faut bien stabiliser le doigt (et surtout se rappeler où il était, en cas d’accident) :

Opérations de base

Le pion s’appelle Monsieur Post. Il se promène sur un graphe. À chaque étape de sa promenade, il regarde l’instruction (en se penchant en avant, le cas échéant) :

Il a parfois besoin de revenir à son point de départ :

Parfois Monsieur Post arrive à un carrefour. Pour savoir de quel côté il doit aller, on regarde si le doigt montre une case vide ou une graine.

Si le doigt montre une case vide alors Monsieur Post fait un virage à gauche (il descend vers la droite du graphe) :

Si le doigt montre une graine (voire plusieurs) alors Monsieur Post effectue un virage sur sa droite (il descend vers la gauche du graphe) :

Dans la case montrée par le doigt, il y a deux opérations possibles :

  • incrémentation (semer une graine dans la case, devant le doigt). Ici la main en haut de la photo vient d’effectuer ce semis.

  • décrémentation (enlever une graine de la case). Ici la main en haut s’apprête à retirer une graine dans la case désignée par le doigt :

Addition

Le principe de l’algorithme est que si on incrémente la seconde case après avoir décrémenté la première case, on ne fait que transférer une graine depuis la première case jusqu’à la seconde. Ceci ne modifie pas la somme des contenus des deux cases et on calcule bien une addition. Ici on voit le début d’une décrémentation de la première case (à droite sur la photo ; début du calcul de 3+0) :

En fait l’algorithme revient à transférer les graines de la première case vers la seconde, ce qui a parfois été verbalisé.

Pour essayer de deviner quelle opération a été effectuée entre les deux nombres (de graines dans les deux premières cases) on peut faire des expériences et les consigner dans une table de l’opération (ici clairement identifiée comme une addition, à voir le signe opératoire utilisé) :

Pour expliquer que l’algorithme effectue bel et bien une addition, un élève a tenté de vérifier la présence d’un invariant (la somme des contenus des deux cases est constante) :

Soustraction

Tout d’abord il a été demandé aux élèves de regarder où est la différence entre les programmes d’addition et de soustraction, puis il leur a été demandé ce que fait ce dernier. C’est plus difficile que pour l’addition :

(le 5-2 en haut est la trace écrite d’un calcul de la fonction décrite plus bas)

On constate une erreur de calcul dans la dernière ligne : oubli d’une décrémentation ; erreur fréquente lorsqu’on essaye de mener les calculs avec des grands nombres :

Fonction

Pour la fonction donnée en exemple, il n’y a plus besoin de 3 colonnes comme dans les tables d’addition et de soustraction, mais seulement de deux colonnes (le nombre initial de graines dans la première colonne, le nombre final dans la seconde colonne). On obtient alors un tableau de valeurs de la fonction, mais la notion de colonnes n’est pas toujours naturelle (le tableau fait plus penser à un diagramme sagittal) :

Un élève a essayé de généraliser la machine en y ajoutant deux autres opérations :

Ne sachant pas par quoi il convenait de multiplier ou diviser, il s’est arrêté là, mais un pas a été fait vers une réinvention du langage de programmation FRACTRAN...

Claire Hénou

Les élèves de CE2, CM1 et CM2 de l’école de la Plaine-des-Palmistes ont eux aussi eu majoritairement droit à la version registres.

Les élèves ne pouvant (ou voulant) assister à l’activité ont été chargés de rédiger un reportage sur l’activité. En voici un :

Aujourd’hui ils sont en train de jouer à la machine de Post. On a des cases et des pions et dans chaque case il y a un signe. Alors on a des haricots. On les met dans des trous. Il y a une main...

Addition

Des problèmes de coordination entre membres de l’équipe se sont montrés. Ici, la graine est prélevée ailleurs que dans la case montrée par le doigt :

Les élèves ont eu du mal à choisir combien de graines ils voulaient mettre dans les cases, se contentant souvent de mettre toutes les graines disponibles dans une case, au détriment des autres cases (et de l’équipe voisine, avec laquelle ils étaient censés partager les graines) :

L’avantage d’une grande quantité de graines, c’est que les élèves ont le temps de l’apprentissage (et l’animateur a le temps de s’occuper des autres élèves). L’inconvénient essentiel est qu’ils font plus facilement des erreurs de calcul (oubli d’une incrémentation, semis d’une graine dans la mauvaise case...). Et une fois l’addition effectuée, pour connaître la somme, il faut compter toutes les graines ce qui prend du temps :

En effet, même en CM2, les élèves ne pensent pas forcément à regrouper les graines par quinaires :

L’usage d’une règle a facilité la préparation de la table d’addition (les élèves ne savaient pas encore que c’est une addition) :

Mais les élèves n’utilisaient pas tous une règle, et la notion de tableau à deux dimensions ne leur était pas toujours naturelle :

La trace écrite est intéressante parce qu’elle permet de voir les erreurs de comptage :

Pour cela, il est important que les élèves verbalisent entre eux et le conflit socio-cognitif n’a pas toujours été apparent dans cette école.

Soustraction

Ici des élèves effectuent la soustraction 4-3 :

Ici aussi :

Ici c’est la soustraction 3-2 qui est en cours de calcul :

Les élèves verbalisent plus sur cette activité que sur l’addition :

Une difficulté avec ce programme est qu’il calcule la différence entre la deuxième case et la première. C’est l’ordre inverse de celui dans lequel on énonce la soustraction. Donc dès que les élèves commencent à deviner qu’il s’agit d’une soustraction, des problèmes de latéralisation apparaissent :

Mais avec du soin on peut voir apparaître une table de soustraction correcte :

Fonction

Voici l’état de la machine de Post juste avant de calculer la moitié entière de 3 :

Et juste après avoir calculé la moitié entière de 10 (les élèves de cette école aiment les grands nombres !) :

Le mot « moitié » a été trouvé assez souvent pour décrire l’effet de cette fonction. Et les tableaux de valeurs sont plus connexes que dans l’école visitée la veille :

Mais pas toujours :

Ci-dessus on voit une erreur de calcul (incrémentation de trop), la moitié entière de 15 étant 7 et non 8.

Multiplication

Les élèves les plus rapides et passionnés sont allés jusqu’à vouloir effectuer une multiplication.

Mais pour corser la difficulté, ils ont décidé d’effectuer une rotation de l’équipe à chaque étape du calcul :

Une tentative de calcul parallèle (prefetch ou pipelining) a été faite :

Si en faisant en même temps, on va plus vite, on risque néanmoins de faire plus d’erreurs de calcul (semis dans la mauvaise case).

Le temps leur a manqué pour finir la multiplication (ils avaient choisi 7×2). D’autant qu’ils ont dû recommencer plusieurs fois à cause d’erreurs dans le calcul :

La présence d’une erreur est identifiable à l’aide d’un invariant : chaque fois que Monsieur Post retourne en haut du bloc du milieu, il y a autant de graines dans la case 3 et la case 4. Ci-dessus ce n’est pas le cas.

Analyse

Ce fut l’occasion de voir aussi comment se trompaient les élèves, notamment avec la version registres. Leurs erreurs ont été analysées avec la programmation Python :

Construction du nombre

Il n’y a pas que les nombres entiers que l’on puisse construire :

  • Hamilton au début du XIXe siècle modélisait un nombre complexe comme un couple de réels, avec les opérations idoines (par exemple (0,1)×(0,1)=(-1,0) pour i²=-1). Encore fallait-il construire les réels.
  • C’est Dedekind qui a effectué cette construction, à l’aide de ce qu’il appelle coupures de rationnels. Une coupure est formée de deux ensembles A et B tels que
    • toute fraction est dans A ou dans B
    • aucune fraction n’est à la fois dans A et dans B
    • aucune fraction de A n’est plus grande qu’une fraction de B.
  • La construction des fractions a été formalisée par Peano mais à partir du livre VII d’Euclide (des proportions) : une fraction est la donnée (en fait, le quotient) de deux entiers. À l’époque des « maths modernes » les fractions étaient le quotient de l’ensemble des couples d’entiers par la relation d’équivalence « le produit des moyens égale le produit des extrêmes ».
  • Toujours à l’époque des « maths modernes », les entiers relatifs étaient le quotient de l’ensemble des couples d’entiers par la relation « la somme des moyens égale la somme des extrêmes ». Donc la construction est similaire à celle des fractions (positives) vue ci-dessus, et Conway fait la remarque qu’on peut construire les fractions de deux manières :
    • on commence par construire les entiers relatifs (une fois construits les entiers naturels) puis on utilise la construction des fractions à partir de couples d’entiers relatifs (c’est le choix effectué par les « maths modernes »),
    • ou on commence par construire les fractions positives, et ensuite on leur applique la construction des relatifs vue ci-dessus pour aboutir aux fractions relatives. Conway conseillait cette seconde approche, historiquement plus cohérente.
  • Les décimaux sont des fractions particulières (dont le dénominateur est une puissance de 10). On peut aussi commencer par construire les décimaux par décalage de virgule (ce qui revient à diviser par 10) et ensuite seulement étendre aux fractions, alors définies comme nombres dont l’écriture décimale est ultimement périodique. Cette approche, pratiquée avant les « maths modernes » nécessite cependant d’aborder l’infini.
  • les fractions dyadiques peuvent se définir de façon analogue aux décimaux : une fraction dyadique est obtenue en divisant un entier par 2 plusieurs fois de suite. Le premier à leur accorder de l’attention a été John Horton Conway dans les années 1970.
  • Mais la base de toutes les constructions de nombres, c’est encore celle des entiers naturels, axiomatisée par Peano à la fin du XIXe siècle. On va détailler celle-là avec comparaison des approches notamment en ce qui concerne les 5 opérations.

Peano utilise la fonction successeur pour construire les entiers. Cette fonction est liée à la construction des ordinaux par Von Neumann (chaque ordinal est l’ensemble contenant les ordinaux inférieurs à lui). Cette construction permet de rapidement aller vers la relation d’ordre des entiers : chaque entier est inférieur à son successeur. La fonction successeur pose un problème concernant la notion de l’infini : tout entier naturel possède un successeur, autrement dit, lorsqu’un enfant sait compter jusqu’à mille, il sait aussi compter jusqu’à mille et un, euh non, mille deux, etc. Comprendre qu’il n’y a pas de réponse possible à la question « jusqu’où sais-tu compter ? » est une approche de l’infini potentiel. À partir de quel âge un enfant peut-il comprendre cela ?

Le modèle des machines à registre donne au contraire une place importante à la fonction partielle prédécesseur. Cette fonction est partielle parce que, contrairement à la fonction successeur, il existe un entier (1 pour Peano, 0 en informatique) qui n’a pas de prédécesseur. Il est d’ailleurs important qu’un entier n’ait pas de prédécesseur, c’est ce qui garantit que les programmes bien conçus terminent en un temps fini : si je demande de compter à rebours, je sais combien de temps cela prendra, si je demande de compter le plus loin possible, cela peut prendre un temps infini...

Le prédécesseur permet de comparer récursivement deux entiers : comparer un entier avec 0 est facile (c’est 0 le plus petit des deux) et sinon, comparer deux entiers revient à comparer leurs prédécesseurs ce qui est plus facile puisque les prédécesseurs sont plus petits.

Les 5 opérations ont une interprétation plus simple en terme de cardinaux (taille d’une collection) que d’ordinaux :

  • La somme de deux cardinaux est le cardinal de la réunion disjointe des deux collections. C’est ce que fait la machine à registres mais c’est aussi la base du calcul des probabilités.
  • La différence entre deux cardinaux est le cardinal de la différence ensembliste, sous réserve que le plus petit cardinal soit inclus dans l’autre. C’est l’approche « complément » dans la typologie de Vergnaud.
  • Le produit de deux cardinaux est le cardinal du produit cartésien (on accouple les élements des deux ensembles de toutes les manières possibles). C’est la définition de la multiplication comme addition itérée qu’on verra plus bas.
  • Le cardinal d’un ensemble quotient est, on s’en doute, un quotient d’entiers. Par exemple, en considérant que deux événements sont survenus à la même heure s’il s’est écoulé un nombre entier de jours entre les deux, on n’a que 24 heures possibles dans une journée.
  • Le nombre de fonctions d’un ensemble A dans un ensemble B est la puissance Card(A)-ième de Card(B). Par exemple, il y a 32 manières de colorier en deux couleurs les 5 solides de Platon.
  • En fait même la relation d’ordre peut être expliquée par les cardinaux, avec l’inclusion d’une collection dans une autre (avec les ordinaux de Von Neumann c’est l’appartenance et non l’inclusion).

Voyons maintenant comment Peano définissait les 5 opérations :

Addition

Peano définit l’addition ainsi :

a + (b+1) = (a+b) +1

Autrement dit, la somme de a et du successeur de b est le successeur de a+b. En ajoutant que a+0=0, on définit l’addition comme une incrémentation itérée.

Avec la machine à registres, on utilise une formulation équivalente mais basée sur la fonction prédécesseur :

  • si b=0, a+b=a
  • sinon, la somme de a et b est la somme du successeur de a et du prédécesseur de b.

Cela revient à transférer une par une les graines de la case b vers la case a et donc de réunir deux collections en une seule.

Soustraction

Pour Peano, la différence x=b-a entre b et a est l’unique solution de l’équation x+a=b. Peano définit donc la soustraction comme une addition à l’envers (l’inverse d’une augmentation chez Vergnaud). Avec la machine à registres par contre, comme on ne fait qu’itérer à tour de bras, on voit plutôt la soustraction comme une décrémentation itérée :

  • si b=0, a-b=a (soustraire du rien revient à ne rien faire).
  • sinon la différence entre a et b est la différence entre leurs prédécesseurs.

L’équivalent chez Vergnaud est la relation de comparaison : on ne modifie pas celle-ci si on incrémente les deux quantités, ou si on les décrémente.

Multiplication

Peano définit la multiplication ainsi :

  • a×1 = a
  • a×(b+1) = a×b+a

Une multiplication est donc une addition itérée. La traduction moderne des axiomes de Peano donne

  • le produit d’un entier a par 0 est nul (égal à 0).
  • le produit de a par le successeur de b est la somme de a×b et a.

En version machine à registres cela se traduit avec le prédécesseur :

  • a×0 = 0
  • Si b n’est pas nul, a×b est la somme de a et du produit de a par le prédécesseur de b.

Division

Pour Peano, on dit que x est le quotient de b par a si et seulement si x×a=b. Peano définit donc la division comme une « multiplication à l’envers » (voir Vergnaud). Gerbert d’Aurillac par contre ramenait la division à une soustraction itérée. Cette dernière définition colle bien avec les machines à registre, et se trouve déjà chez Euclide (tome VII des Éléments). Elle est liée à la propriété archimédienne des entiers (quelle que soit l’ampleur non nulle d’un pas entier, il faut un temps fini pour atteindre un seuil donné ; le nombre de pas est le successeur du quotient euclidien et on a dépassé le seuil d’une valeur égale au reste euclidien, s’il y en a un).

Exponentiation

Suivant la logique de ce qui précède, l’exponentiation est une multiplication itérée (Donald Knuth et John Conway se sont d’ailleurs rapidement demandé pourquoi s’arrêter en si bon chemin).

Alonzo Church, avec ses numéraux, a construit lui aussi le nombre (entier) mais à partir de fonctions. Noter qu’avec les numéraux de Church, la plus simple à définir parmi les 5 opérations, est l’exponentiation.

Finalement, une autre construction du nombre est apparue dans les années 1970, elle est dûe à John Conway et généralise les coupures de Dedekind. Elle s’appuie sur la théorie des jeux combinatoires (Conway cherchait à quantifier l’avantage d’un joueur à un jeu) et Conway considérant comme plus simples des nombres apparus plus tôt dans la construction, les nombres les plus simples selon Conway sont, dans l’ordre de complexité croissante :

  1. le nombre 0
  2. les nombres -1 et 1
  3. les nombres -2, -1/2, 1/2 et 2
  4. les nombres -3, -3/2, -3/4, -1/4, 1/4, 3/4, 3/2 et 3
  5. etc.

Ainsi, pour Conway, le nombre 1/2 est plus simple que le nombre 3. La moitié est-elle une notion plus évidente que le triple ? En tout cas, les nombres négatifs viennent très tôt chez Conway puisque pour inverser le signe d’un nombre, il suffit d’intervertir les rôles des deux joueurs (un nombre négatif est pour moi un jeu où je perds).

Cycle 2

Les machines à registres ont été présentées dans 3 classes de l’école Aristide Briand au début de l’année 2022. L’accueil par les enseignants et aussi par les élèves, donne envie de continuer l’expérience en cycle 2.

CP a

Le lundi 1er février 2022, l’atelier a été testé dans de bien meilleures conditions (en terme d’effectif et de durée) en classe de CP (école Aristide Briand). Voici le compte-rendu :

Un groupe d’élèves a même eu le temps d’effectuer une multiplication (en CP !) :

Programmes

On constate

  • une nette tendance à utiliser chaque instruction une et une seule fois,
  • des difficultés à dessiner (et probablement à voir) les pointes de flèches,
  • une tendance à croiser les flèches,
  • une certaine ressemblance avec les graphes tracés l’année dernière (en GS) par les mêmes élèves (visibles dans cet article) :

Deux algorithmes originaux ont cependant été produits, on les présente dans les deux onglets suivants.

Alyassa

On voit ici l’histoire se construire. Voici le brouillon d’Alyassa :

Puis il a décidé de refaire ce graphe de manière plus visible :

Ce programme est non seulement presque (la case testée n’est pas la bonne) correct, mais aussi original. Que fait-il ? La partie « ?H » signifie qu’on fait le reste tant qu’il y a des graines dans la case présente. Le reste, est décomposable en trois blocs d’instructions :

  1. Deux « + » qui font ajouter deux graines dans la case présente,
  2. un « ←-→ » qui fait enlever une graine dans la case voisine de gauche,
  3. deux autres « + » qui font ajouter deux graines à nouveau.

Le ←-→ est une action par conjugaison (on conjugue le « - » par une translation « → » ce qui a pour effet d’appliquer le « - » à côté) de la théorie des groupes. Par ailleurs, les trois blocs d’instruction « commutent » ce qui veut dire que ce programme a exactement le même effet que

  1. Deux « + » qui font ajouter deux graines dans la case présente,
  2. deux autres « + » qui font ajouter deux graines à nouveau,
  3. un « ←-→ » qui fait enlever une graine dans la case voisine de gauche.

et donc que

  1. Quatre « + » qui font ajouter quatre graines dans la case présente,
  2. un « ←-→ » qui fait enlever une graine dans la case voisine de gauche.

En dehors de l’erreur sur la case à vérifier, il s’agit donc d’un programme de quadruplement.

Lucy

Le programme de Lucy lui aussi, est original :

Il y a deux interprétations possibles, selon que Lucy a fait, ou non, une erreur de latéralisation. Si elle a échangé la gauche et la droite, le programme s’arrête lorsque le doigt pointe une case vide. Sinon, on sème une graine puis on va à la case suivante et on enlève une graine. La condition d’arrêt du programme est donc que le doigt est arrivé sur une case où il n’y avait, initialement, qu’une graine. L’algorithme de Lucy vise donc à ajouter une graine à toutes les cases consécutives qui en contenaient déjà plusieurs. Par exemple, en commençant sur ce tableau

3 2 5 4 1 2 3 0

il s’arrête sur

4 3 6 5 0 2 3 0

Mais si par contre Lucy n’a pas échangé la gauche et la droite, son programme reste intéressant et original. Il s’arrête à la première case qui ne contient pas une graine unique, et tant que le doigt est devant une case contenant une graine, il l’enlève puis la remet. Par exemple sur ce tableau

0 1 1 1 1 3 1 1

il donne

1 1 1 1 1 2 1 1

mais le doigt devant la case à 2 graines.

Récits d’élèves

En cliquant sur un des schémas ci-dessous on peut télécharger le récit complet au format pdf :

CP b

La classe de CP b de la même école a eu droit à l’activité le jeudi 10 février 2022 :

L’idée discutée à la fin de la séance est intéressante à expérimenter un jour de beau temps :

  • le graphe serait tracé (à la craie par exemple) par terre,
  • le rôle de Monsieur Post serait interprété par un.e élève,
  • le doigt serait incarné par un.e autre élève,
  • les instructions seraient dessinées sur des étiquettes que Monsieur Post lirait à voix haute,
  • les graines seraient remplacées par des ballons,
  • la mémoire serait matérialisée par un alignement de bacs.

CE1 b

Et la classe de CE1 b de la même école a semé des graines le lundi 14 février 2022 :

CE2

Un livret a été préparé pour la visite d’une classe de CE 2 (cliquer sur l’image pour avoir le pdf) :

Il comprend 15 fiches d’exercices à mener éventuellement sans la machine de Post. Ce livret a été distribué aux RMC de l’académie le lundi 9 mai, avec cette présentation :

Pendant ce temps, une classe de CE 2 (école Aristide Briand) a pu manipuler des machines de Post pour faire les fiches des pages 2 à 13.

page 2

Exemple de recherche d’état final selon la modélisation de Vergnaud : on connaît

  • l’état initial (1 graine)
  • la transformation (ajout de 2 graines)

et on demande l’état final :

Parmi les (rares) erreurs constatées, on voit

  • le dessin des seules graines ajoutées (et pas de l’ancienne graine)
  • le dessin des graines sur l’état initial au lieu (ou en plus) de l’état final.

On remarque une tendance à dessiner les 3 graines en triangle, ce qui n’est pas le cas sur un dé ou un domino.

page 3

Une soustraction cette fois-ci. Certains élèves recopient l’état initial puis barrent les graines récoltées, ce qui évoque le dessin des nombres négatifs dans TiPont974 :

page 4

Comme le doigt bouge avant le semis, celui-ci ne s’effectue pas sur la case de départ mais sur celle d’à côté :

La graine semée à gauche est une conséquence probable de la disposition des élèves face à face ce qui fait que certains voyaient la machine de Post à l’envers.

Les 6 graines pourraient venir d’une inversion de l’ordre d’exécution des instructions. Mais cela n’explique pas que parfois les 6 graines sont dans la case de droite.

On voit aussi parfois une volonté de dessiner non seulement la position finale du doigt mais aussi toutes les positions intermédiaires.

page 5

Un agriculteur ne fait pas que semer et récolter, il faut aussi qu’il sache piloter son tracteur :

On voit une tendance à dessiner non seulement la position finale du doigt mais aussi les positions intermédiaires.

Le doigt n’a pas toujours bougé durant l’exécution du programme.

page 6

Taux de réussite élevé :

On peut comparer les stratégies utilisées pour dessiner les graines.

page 7

Taux de réussite important (les élèves ont bien compris qu’il fallait ajouter 3 graines, quitte à barrer la 4e qui est ensuite enlevée) :

On remarque que souvent pour dessiner les 3 graines supplémentaires on recopie celles qui sont déjà présentes.

page 8

L’algorithme se résume à un transfert de deux graines, de la case actuelle vers sa voisine de gauche :

Le taux de réussite est élevé mais

  • la récolte initiale des 2 graines (avant de les resemer) a parfois été oubliée
  • elle a aussi été remplacée par un semis
  • trois graines ont été récoltées au lieu de 2.

Le dessin à l’envers vient d’une élève qui faisait face à sa coéquipière et elle a dessiné l’état final de la machine telle qu’elle le voyait (voir onglet suivant).

page 9

Les élèves se faisant face avec la machine de Post entre eux, celle-ci n’était tournée correctement que pour l’un d’entre eux. Ce qui peut expliquer que parfois les deux graines aient été semées à gauche plutôt qu’à droite :

Parfois le mouvement du doigt est oublié et les graines sont semées dans la case de départ. Mais plus surprenant il arrive que les 5 graines au total soient recopiées dans la case de droite, comme si les 3 graines avaient été transférées, en plus des semis.

page 10

Un problème de type recherche d’état initial à la Vergnaud (le doigt ne bouge pas) :

Certains élèves ont d’abord cherché à appliquer la transformation (une double incrémentation) à l’état final puis se sont ravisés, et n’ont pas toujours utilisé la gomme pour revenir à l’énoncé.

On voit aussi, à deux reprises, une confusion entre état et transformation ce qui aboutit à deux graines au lieu d’une dans la case de l’état initial.

page 11

Exercice complexe même s’il n’y a que deux instructions dans le programme. Il semble y avoir assez souvent une confusion entre le mouvement du doigt et les semis et récoltes. En fait il y a une tendance à seulement permuter les instructions élémentaires sans les modifier :

Essayer d’appliquer les opérations à l’état final est assez fréquent sur cette activité. Les deux seules élèves qui ont donné une réponse correcte, se sont trompées sur la première case : elles ont ajouté deux graines alors qu’après en avoir enlevé une, la case était vide.

page 12

La machine de Post n’aide pas beaucoup pour cet exercice complexe, car même si on a deviné l’état initial, après vérification, on a oublié les détails. Il faudrait a minima une deuxième machine pour mémoriser l’état initial. D’ailleurs l’état final a parfois été utilisé comme brouillon.

On constate là encore une certaine tendance à appliquer le programme à l’état final, et à dessiner les états intermédiaires sur la fiche.

page 13

Le programme se simplifie en une décrémentation, donc on demande quel état initial donne 2 après une décrémentation. Peu d’élèves ont eu le temps de commencer cette page et tous ont trouvé 4 au lieu de 3, sauf celle qui a appliqué la transformation à l’état final :

Bilan

En raison de l’absence d’une enseignante, plusieurs élèves de CP b, qui avaient déjà manipulé la machine (voir plus haut), ont été placés en CE 2. Ils ont insisté pour faire les fiches avec les élèves de CE 2 mais il n’y avait pas assez de fiches pour eux. Ils se sont montrés assez déçus.

Plusieurs élèves de CE 2 se sont montrés réticents à l’idée de confier leurs livrets (pour scanner) car ils n’avaient pas fini les fiches. Il a fallu leur promettre de leur rendre les fiches après le scan.

Il y a même eu des élèves qui ne voulaient pas aller en récréation tant ils préféraient jouer à la machine de Post !


[1Il est d’ailleurs décédé des suites d’une électrothérapie en 1954.

[2Il suffit pour cela d’utiliser un tri topologique sur le graphe.

[3On remarque que la verbalisation fait plus souvent appel à l’expression « jusqu’à ce que » qu’à l’expression « tant que » (while de Python). Probablement parce qu’elle évite de charger la mémoire de travail avec une négation.

[4Quand le sage pointe l’index, l’enfant regarde le pouce (d’après Confucius).

[5Les machines à 2 registres ont déjà été expérimentées dans le premier degré par Yves Lafont, mais ici il n’y pas besoin de nommer les registres, puisque l’index pointe sur l’un d’entre eux.

[6Cela peut aller jusqu’à la découverte des nombres premiers !

[7Il s’agit d’ailleurs d’un langage de programmation appelé P’’ et datant des années 1960.

[8Le prédécesseur d’un nombre est celui qui vient juste avant lui dans la comptine. Comme le prédécesseur d’un nombre est plus petit que lui, on aboutit donc à une simplification du calcul. Par exemple en calcul mental si je dois calculer 35-17 je soustrais d’abord 10 aux deux opérandes : 25-7 donnera le même résultat. Puis je soustrais 5 aux opérandes parce que 20-2 donne le mếme résultat 18.

[9Contextualisé cela donne « j’avais 5 litchis, j’en ai mangé 3, combien m’en reste-t-il ? » Alors je peux imaginer que j’ai mangé les 3 litchis un par un et je suis passé successivement par les étapes

  • j’ai 5 litchis, je vais en manger 3 en tout,
  • après avoir mangé un litchi, il m’en reste 4 et je vais en manger encore 2, un par un,
  • après avoir mangé un nouveau litchi il m’en reste 3 et je vais encore en manger un,
  • alors il m’en reste 2 et j’en ai mangé 3 donc j’arrête.

Documents joints

Scalable Vector Graphics - 1.2 ko
PDF - 12 ko

Commentaires