machine de Post-Wang

Multiplication par la machine de Post-Wang

Pour effectuer le produit de 3 par 4, on commence par cocher 3 puis 4 cases consécutives (séparées par une seule case non cochée) de manière à avoir la suite "11101111". En plaçant Mario au-dessus de la première case cochée, il va effectuer le produit, en ayant coché autant de cases que le produite comporte d'unités (par exemple, 12 cases consécutives) à la fin. On pourrait fort bien écrire un seul programme (il suffit de copier-coller un programme complet dans une des fenêtre). Cependant, la complexité de l'algorithme incite à donner trois programmes successifs à exécuter, et c'est ce que l'on va faire ici à titre pédagogique :

Comme la bande est binaire, il faut ajouter avant chaque nombre une case cochée supplémentaire, qui sert d'adresse mémoire. Le premier programme sert donc à préparer la suite, en cochant une case devant (ou derrière) chaque facteur, et une case pour l'instant seule, destinée à repérer le produit.

Le second programme est le plus long, il fait une double boucle:

effacer une case du premier facteur, puis
recopier le second facteur après le produit (car 3×4=4+4+4), ce qui se fait encore dans une boucle :
- effacer provisoirement une des cases du second facteur;
- ajouter une case cochée tout à la fin
- revenir à la case précédemment effacée
- la restaurer, puis boucler

Après l'exécution du programme 2, il y a donc, à cause du programme 1, une case de trop cochée pour le second facteur et le produit (le premier facteur a été effacé). Le troisième programme efface le second facteur et enlève la case de trop pour le produit, ce qui permet alors à Emilio de poser fièrement devant le produit.

Instructions du langage

aller à gauche pour faire aller Emilio vers la gauche (d'un pas)
aller à droite pour faire aller Emilio vers la droite
marquer la case pour que Emilio coche (ou laisse cochée) la case
effacer la case pour qu'Emilio efface la case (ou la laisse effacée)
aller à la ligne 5 pour revenir à la ligne 5 du script
si coché alors aller à la ligne 5 a pour effet de revenir à la ligne 5 du script si Emilio voit une case cochée à ses pieds
si vierge alors aller à la ligne 5 a pour effet de revenir à la ligne 5 du script si Emilio voit une case non cochée à ses pieds
prendre un café a pour effet de ne rien faire (sauf passer à la ligne suivante)
stop arrête tout

Les programmes :

Programme 1	Programme 2	Programme 3
aller à droite si vierge alors aller à la ligne 4 aller à la ligne 1 marquer la case aller à droite effacer la case aller à droite si vierge alors aller à la ligne 10 aller à la ligne 7 marquer la case aller à droite marquer la case aller à droite aller à droite marquer la case aller à gauche	aller à gauche si effacé alors aller à la ligne 5 aller à gauche aller à la ligne 2 aller à gauche si effacé alors aller à la ligne 9 aller à gauche aller à la ligne 6 aller à droite effacer la case aller à droite si effacé alors aller à la ligne 40 aller à droite si effacé alors aller à la ligne 17 aller à droite aller à la ligne 14 aller à droite aller à droite si effacé alors aller à la ligne 1 effacer la case aller à droite si effacé alors aller à la ligne 25 aller à droite aller à la ligne 22 aller à droite si effacé alors aller à la ligne 29 aller à droite aller à la ligne 26 marquer la case aller à gauche si effacé alors aller à la ligne 34 aller à gauche aller à la ligne 31 aller à gauche si effacé alors aller à la ligne 38 aller à gauche aller à la ligne 35 marquer la case aller à la ligne 18	aller à droite si vierge alors aller à la ligne 5 effacer la case aller à la ligne 1 aller à droite effacer la case aller à droite

Programme 1

Programme 2

Programme 3

Multiplication par la machine de Post-Wang

Instructions du langage

Les programmes :

Ne pas oublier de stopper l'animation avant de changer de programme !