Pico pense à un nombre, par exemple 8 (on verra ci-dessous l’intérêt qu’il y a à commencer par une puissance de 2). Il marche sur le chemin, jusqu’à ce qu’il rencontre une fraction, ici 2,5. Chaque fois qu’il rencontre une fraction, il la multiplie par son nombre, ici 2,5×8=20. Comme le produit est entier, Pico remplace son nombre (qui jusque là était 8) par le produit 20. Et, chaque fois que Pico change de nombre, il est téléporté au départ, d’où il repart avec le nouveau nombre.

Ainsi, après son premier retour à la case départ, Pico pense au nombre 20, jusqu’à sa rencontre, encore une fois, avec la fraction 2,5. Comme 2,5×20=50 est encore un entier, Pico est téléporté encore une fois au départ, en pensant maintenant à 50. Et c’est avec 50 à l’esprit qu’il recommence la course, jusqu’à la première fraction. Or 2,5×50=125 qui est encore entier, et Pico est à nouveau téléporté au départ, en pensant à 125.
Arrivé à la première fraction, et non sans une certaine lassitude, Pico multiplie alors son nombre 125 par la valeur 2,5 de la fraction, et le produit 312,5 n’étant pas entier, Pico continue alors son chemin, en continuant à penser à 125. Mais hélas pour lui, il trouve alors sur son chemin une nouvelle fraction, de valeur 0,12, et le produit de cette fraction par 125 valant 0,12×125=15 est entier : Bien qu’il soit enfin arrivé au milieu du chemin, Pico doit tout recommencer, en pensant cette fois au nombre 15.
Arrivé à la première fraction, il multiplie 15 par 2,5 et 15×2,5=37,5 qui n’est pas entier. Ce qui remplit Pico d’espoir puisque cela lui permet de continuer le chemin. Arrivé à la seconde fraction, Pico effectue le produit de 0,12 par 15 et trouve 1,8 qui n’est pas entier non plus : Pour la première fois depuis le début de l’histoire, Pico peut enfin continuer son chemin. Mais cela le mène à la dernière fraction, de valeur 0,2, et, au grand désespoir de Pico, 15×0,2=3 est entier : Pico n’a plus qu’à tout recommencer.
Il repart donc du début, en pensant au nombre 3. En arrivant à la première fraction, il multiplie 3 par 2,5 et constate avec un certain espoir, que le résultat 7,5 n’est pas entier. Il continue donc son chemin et, arrivé à la seconde fraction, effectue 0,12×3=0,36 qui n’est pas entier non plus. Il se dirige alors avec courage et appréhension vers la troisième fraction. Là il effectue 0,2×3=0,6 qui n’est pas entier non plus, et peut continuer son chemin. Mais il n’y a maintenant plus de fraction, et Pico arrive au bout toujours en pensant au nombre 3.
On pourrait s’intéresser à la suite des nombres auxquels a pensé Pico à chaque départ du circuit :

Nombres trouvés par Pico en fonction des étapes

La ressemblance avec la suite de Collatz n’est pas tout-à-fait fortuite : C’est dans le cadre de recherches sur cette suite, que Conway a inventé Fractran.
Cependant, pour faire plus simple, on va se concentrer sur le lien entre le nombre de départ (ici 8) et le nombre d’arrivée (ici 3), ce qui définit une fonction sur les entiers naturels non nuls. En voici la table :

Difficile d’émettre une conjecture avec ces nombres, mais en ne regardant que les puissances de 2 on y voit mieux :

On peut alors conjecturer que :

• Lorsqu’on commence par penser à une puissance de 2, on finit en pensant à une puissance de 3 ;
• L’exposant de la puissance de 3 finale est la moitié de l’exposant de la puissance de 2 du départ.

Pour démontrer cette conjecture, on va changer de registre avec les registres de Minsky.

C’est dans les années 1960 que Marvin Minsky a inventé un modèle de calculabilité différent des précédents [3], afin de démontrer un théorème sur les machines de Turing minimales. Ce modèle est plus proche de la réalité que le sont le lambda-calcul (qui, parmi les lecteurs, possède une machine basée sur le lambda-calcul ?) ou les machines de Turing (qui en a déjà touché une ?) : Par exemple le Raspberry Pi 2, avec ses 4 cœurs, possède 32 registres par cœur soit 128 registres ; et la Ti 82 basée sur un microprocesseur Z80 est dotée de 7 registres A, B, C, D, E, H et L.

Photographie au microscope électronique des registres A, B et C (ces deux derniers sont appariés) du Z80 ; la longueur fait un peu plus d’1 mm

Une machine à registres est donc une sorte d’ordinateur minimal, en ce que les seules opérations effectuées sur les registres sont

• le test de nullité (aller à une ligne déterminée si le registre est vide)
• l’incrémentation (augmenter le contenu du registre d’une unité)
• la décrémentation (si le registre n’est pas vide, diminuer son contenu d’une unité).

Ce modèle est capable de calculer toute fonction calculable. La clé du changement de cadre entre Fractran et les registres de Minsky est dûe à Kurt Gödel [4], et est basée sur l’unicité de la décomposition en facteurs premiers. On peut dire que

• tout entier naturel n peut être représenté de façon unique par un entier non nul, à savoir 2ⁿ ;
• tout couple d’entiers naturels (par exemple, un point à coordonnées entières x et y) peut être représenté de manière unique par un seul entier non nul : 2^x×3^y par exemple.
• Tout triplet d’entiers naturels a, b et c peut, de façon similaire, être représenté de façon unique par un entier non nul, à savoir 2^a×3^b×5^c ;
• Et de façon générale, tout tuple d’entiers naturels peut être représenté de manière unique par un entier non nul. C’est l’unicité qui découle de celle de la décomposition en facteurs premiers, de l’entier en question.

On appelle codage de Gödel, l’opération consistant à calculer l’entier représentant un tuple, et décodage de Gödel l’opération inverse, qui, à partir d’un entier, donne par décomposition en facteurs premiers, le tuple représenté. Chaque coordonnée du tuple est appelée un registre. Dans l’exemple ci-dessus, on constate que les facteurs premiers intervenant dans les fractions sont uniquement 2, 3 et 5 ; on va donc modéliser par un entier de Gödel, les contenus de trois registres, que l’on notera r2, r3 et r5 :

Comme le registre 2 contient 11 graines, et que les autres registres sont vides, le nombre de Pico est 2¹¹×1×1=2048. Ce nombre étant pair, son produit par 2,5 est entier, et s’obtient en

• divisant le nombre par 2 ce qui a pour effet de diminuer d’une unité le contenu du registre 2 (décrémentation) ;
• multipliant le nombre par 5, ce qui a pour effet d’augmenter d’une unité (incrémenter) l’exposant de 5 dans la décomposition en facteurs premiers.

Ici 2¹¹×1×1 devient, après multiplication par 5/2, le nombre 2¹⁰×1×5=5120. Le mouvement correspondant consiste à enlever une graine du registre 2 et ajouter une graine (tant qu’à faire, la même) dans le registre 5 :

En fait, tant qu’il y a des graines dans le registre 2, la fraction 5/2 donnera un résultat entier, puisqu’elle est multipliée par un nombre pair : Son effet est donc de transférer une par une les graines du registre 2 vers le registre 5, jusqu’à ce que le registre 2 soit vide. On peut appeler cela “vider le registre 2 dans le registre 5” :

Ce vidage de r2 dans r5 a eu pour effet de “remplacer” le nombre 2048 par 5¹¹=48828125. Ce simple remplacement permettra, plus bas, de simplifier le programme Fractran étudié. Pour l’instant on constate qu’aucun numérateur n’étant pair, le registre 2, une fois vide, le reste, et la première fraction ne donnera plus de résultat entier : C’est à partir de maintenant la fraction 3/25 qui va agir. La division par 25 équivalant à deux divisions successives par 5, la multiplication par 3/25 revient à

• enlever 2 graines du registre 5 ;
• en ajouter une des deux au registre 3 (l’autre part, a priori, à la poubelle) :

Autrement dit, le produit de 5¹¹=48828125 par 3/5² est 3×5⁹=5859375. La graine restante a été placée devant les registres. Tant que le nombre est divisible par 25, on répète cette opération de transfert d’une graine du registre 5 vers le registre 3 accompagnée de la sortie pure et simple d’une autre graine du registre 5. On obtient successivement les nombres 3²×5⁷=703125, 3³×5⁵=84375, 3⁴×5³=10125 et 3⁵×5¹=1215. Alors la moitié des graines qui étaient dans le registre 5 a été transférée dans le registre 3, et l’autre moitié est restée hors registres :

En fait, ce n’est pas exactement la moitié des 11 graines qui sont dans le registre 3, puisque 11 est impair, et il reste une graine dans le registre 5. L’effet de la dernière fraction (division par 5) est justement d’enlever cette éventuelle graine restante :

Du point de vue des codages de Gödel, on est passé de 3⁵×5¹ à 3⁵ : L’exposant initial de 2 était 11 et l’exposant final de 3 est 5 qui est bien le quotient euclidien de 11 par 2.
Le programme se traduit ainsi en Sofus :

Les machines à registres présentent plusieurs avantages sur Fractran :

• Un tuple comme (3,1,2) occupe moins de place en mémoire, que l’entier de Gödel 600 qui le représente [5] ;
• Les calculs sur registre (incrémentation, décrémentation) sont plus rapides ou consomment moins d’énergie, que les multiplications et divisions [6] de Fractran ;
• On risque moins de dépassement de capacité avec les incrémentations qu’en multipliant des grands entiers.
• On évite les lourdes opérations de codage et décodage de Gödel avec la programmation directe des registres.

La fraction 5/2 ne sert qu’à transférer (et non copier) le registre 2 dans le registre 5 ; on peut donc s’en passer, en utilisant directement le registre 2 à la place du registre 5 :

Trois simplifications ont été faites :

• remplacer tous les r5 par des r2
• enlever r5
• enlever le transfert

On travaille maintenant sur deux registres, en enlevant les graines 2 par 2 du registre r2, mettant la moitié dans le registre 3, puis en enlevant l’éventuelle dernière graine du registre 2 :

Du point de vue de Fractran, deux simplifications ont été faites :

• suppression de la première fraction ;
• remplacement des 5 par des 2 dans les décompositions en facteurs premiers des numérateurs et dénominateurs des fractions restantes.

Le programme Fractran simplifié devient $\left( \frac{3}{4},\frac{1}{2} \right)$ et il a exactement le même effet que le précédent : Transformer une puissance de 2 en une puissance de 3, dont l’exposant est la moitié de l’exposant initial. Mais on peut imaginer une “simplification” supplémentaire, en supprimant la dernière fraction, qui servait à vider le registre r5 : Le programme Fractran constitué de l‘unique fraction ¾ a pour effet de transformer 2^a en 3^q×2^r où q et r sont respectivement le quotient et le reste dans la division de a par 2.

Si on représente l’état des trois registres par un point ayant

• en abscisse, le nombre de jetons dans le registre r2 ;
• en ordonnée, le nombre de jetons dans le registre r3 ;
• en cote, le nombre de jetons dans le registre r5,

alors chaque fraction peut être représentée par un vecteur à additionner au point actuel, pour avoir le point suivant. L’addition se fait cependant de façon conditionnelle, en effet on ne l’effectue pas si le résultat a une coordonnée négative Dans Sofus, les contenus des registres sont les coordonnées d’un vecteur nommé U, et la détection d’un signe négatif parmi ces coordonnées se résume par le mot problème :

En cas de problème suite à l’addition d’un vecteur, il faut soustraire à nouveau le vecteur pour corriger le problème. Sinon on passe à la suite. Voilà comment les fractions sont modélisées par des additions de vecteurs :

5/2	3/25	1/5

Avec ce modèle, le programme Fractran ci-dessus devient ceci, en Sofus :

On remarque la présence d’une boucle sans fin, que le dernier bloc permet de quitter quand même, une fois que toutes les multiplications par des fractions additions de vecteurs ont échoué.

Pour additionner des vecteurs, d’autres logiciels que Sofus sont plus adaptés : R, qui ne connaît pas de limite sur le nombre de registres, ou les logiciels de géométrie dynamique pour des vecteurs de dimension 2 ou 3 que l’on voit ici. Par exemple, en partant du point A(3,0,0) correspondant à l’entier 8 choisi au départ, la trajectoire du calcul Fractran est celle-ci :

Chaque vecteur vert correspond à la fraction 5/2, le vecteur bleu correspond à la fraction 3/25 et le vecteur rouge, à la fraction 1/5.

Comme GeoGebra a un mode anaglyphe, les lecteurs non daltoniens munis de lunettes rouge-cyan peuvent même voir cette trajectoire en relief (mais sans les couleurs) :

Voici les fichiers utilisés :

fichier Sofus	fichier ggb

La version simplifiée du programme avec deux fractions (3/4,1/2) fait appel à des vecteurs de dimension 2, ce qui donne cette trajectoire :

Et, avec un nombre initial de 128 (représenté par le point A(7,0) puisque 128=2⁷) :

Ce dessin montre, par la pente des vecteurs bleus, pourquoi il s’agit d’un programme de division par 2.

Les systèmes d’addition de vecteurs présentent sur les fractions de Fractran ou les registres de Minsky, deux avantages :

• On peut avec Sofus, incrémenter un vecteur (ce qui agit sur plusieurs registres à la fois) par un vecteur, avec le « augmenter de » si cher à Sofus ;
• On peut, avec la géométrie dynamique, dessiner la trajectoire d’un point sous l’effet des translations successives.

Cependant, les deux modèles ne sont pas équivalents : Le fait qu’on peut additionner un vecteur, ne suffit pas à émuler de façon déterministe un programme Fractran : Encore faut-il savoir dans quel ordre on doit additionner les vecteurs ! Par contre, le modèle des additions de vecteurs est équivalent à celui des réseaux de Petri.

Dans un réseau de Petri, chaque registre est représenté par un cercle (en bleu ci-dessous, on peut imaginer que ce sont les verres de la partie sur les registres) appelé place, les nombres contenus dans les registres, appelés marquage sont représentés par des jetons dans les places, et les fractions sont représentées par des carrés appelés transitions :

Chaque flèche indique soit, en aval de la transition, l’absorption d’un jeton depuis un registre, soit, en amont, l’injection d’un jeton vers un registre. En fait, le programme Fractran ci-dessus n’a pas réellement d’équivalent en réseau de Petri. Par exemple ci-dessus la transition du bas peut vider le registre 3 prématurément et ne permet pas que le nombre final de jetons dans le registre 3 soit égal au quotient euclidien par 2, du marquage initial. Cela signifie que l’algorithme implémenté dans le programme Fractran n’est peut-être pas parallélisable. En tout cas il y a non-déterminisme. En fait il y a quand même quelque chose qui évoque la division euclidienne par 2 avec ce réseau de Petri :

• Lorsque le réseau de Petri se bloque (on ne peut plus y déplacer de jetons), le nombre de jetons dans le registre r3 est inférieur ou égal au quotient par 2 du nombre de jetons initialement dans le registre ;
• Il existe une séquence de transitions permettant d’atteindre ce maximum (3 fois la transition 5/2 puis une fois la transition 3/25 et seulement à la fin, la transition 1/5).

Ces deux résultats se résument à : « ce réseau de Petri effectue faiblement la division euclidienne par 2 ». Leroux et Snœbelen démontrent que dans le cas de fonctions non linéaires comme la division euclidienne, il n’existe pas de réseau de Petri faisant mieux que le calcul faible.

Voici une présentation des réseaux de Petri, dans un contexte plus ludique (généralisation de jeux de Nim) :

article sur Petri	source en LaTeX

De même, la fraction ⅜ effectue la division euclidienne de l’exposant de 2 donné au départ, par 3 ; la fraction 3/16 effectue la division par 4, etc. Il est à remarquer que le programme Fractran de division euclidienne (envoyant 2^a×3^b vers 5^q×7^r) donné sur wikipedia, est nettement plus compliqué puisqu’il utilise 8 fractions.
Une séquence pédagogique non encore testée en classe, consisterait à donner d’abord un programme d’une seule fraction, et à l’utiliser comme outil de calcul moyennant un paiement par décomposition en facteurs premiers. Exemples :
La fraction ⅔, qui transfère le contenu du registre 3 dans le registre 2, est un programme d’addition. Voici un exemple de dialogue possible entre un élève et cette fraction :

On obtient successivement 576, 384, et 256 puis le programme s’arrête parce que 256 n’est pas un multiple de 3, en effet 2+5+6=13 et 1+3=4 ; la conversation reprend alors :

Un dialogue analogue peut être imaginé avec l’unique fraction ⅙, qui est à elle seule un programme de soustraction ; pour lui faire effectuer la soustraction 8-3, on doit calculer 2⁸×3³=6912, qui, divisé successivement par 6, donne 1152, 192, puis 32=2⁵ ce qui donne le résultat de la soustraction : 5.
Une fois que les champions de fractemon sont à l’aise avec les programmes d’une seule fraction, on peut évidemment les faire aller vers d’autres niveaux, où il y a plus de fractions, par exemple avec ce programme de multiplication, formé de 6 fractions :

$\left( \frac{455}{33},\frac{11}{13},\frac{1}{11},\frac{3}{7},\frac{11}{2},\frac{1}{3} \right)$

Là encore, on démarre le programme avec 2^a×3^b pour aboutir à 5^a×b mais c’est beaucoup plus long. On remarque qu’on a besoin de 6 registres, numérotés 2, 3, 5, 7, 11 et 13.

Le circuit ci-dessous est devant le gymnase d’un lycée. Le point de départ est d’ailleurs la position affichée sur Google Maps pour ce lycée. La course se fait, sauf exception, selon les flèches bleues. Mais il y a 3 relais d’étapes comprenant chacun une fraction (un QR-code à flasher ou une sorte de fractemon-go à attraper à l’aide du smartphone). Arrivé à la fraction, le concurrent doit tester la multiplication de la fraction par le nombre qu’on lui a confié au départ, et chaque fois que le résultat est entier, il doit emprunter une flèche rouge avec le nouveau nombre. Lorsqu’il est (enfin) arrivé au point d’étape intitulé “arrivée”, il retourne tranquillement au départ, et fait inscrire son nombre final en regard du nombre qui lui avait été confié au début de la course.

L’expérience devait être réalisée lors de la semaine des maths 2017, mais cela n’a pas pu se faire, pas plus que l’équivalent à plus grande échelle, à Grand-Coude. Cependant, une course d’orientation qui peut servir de base à une telle activité, a déjà été testée par l’un de nous.

Bonus : Un interpréteur Fractran en Python, parce que les fractions en collège c’est bien, mais en lycée c’est pas inutile d’y revenir un peu

from fractions import *
programme = [Fraction(5,2),Fraction(3,25),Fraction(1,5)]
nombre = 2**11				# le nombre de Pico

def estEntier(fraction):
	return fraction.denominator == 1

position = 0				# la position de Pico
while position<len(programme):
	if estEntier(nombre*programme[position]):
		nombre *= programme[position]
		position = 0		# teleport si multiplication
		print nombre
	else:
		position  += 1		# au suivant sinon