Voir la source de FRACTRAN

{{Ébauche|mathématiques}}
'''FRACTRAN''' est un [[langage de programmation exotique]] et [[Turing-complet]] s'appliquant à des [[Entier naturel|entiers naturels]]. Il a été inventé par le mathématicien [[John Horton Conway|John Conway]] qui en publie une description en 1987<ref name="HavilHisto">Julian Havil, ''{{Langue|en|Nonplussed!: Mathematical Proof of Implausible Ideas}}'', p. 162-163.</ref>{{,}}<ref name="Conway" group="note">Dans l'article ''{{lang|en|FRACTRAN: A simple universal programming language for arithmetic}}'', paru dans le livre de [[Thomas M. Cover|Cover]] et Gopinath, ''{{Langue|en|Open Problems in Communication and Computation}}'', Springer-Verlag, New York, (1987), p. 4-26.</ref> ; son objectif est de généraliser le [[Conjecture de Syracuse|problème de Syracuse]], en montrant que des questions de ce type peuvent être [[Décidabilité|indécidables]], car se ramenant au [[problème de l'arrêt]].

== Fonctionnement d'un programme FRACTRAN ==

=== Description des programmes ===
Un programme FRACTRAN est constitué d'une [[Liste (informatique)|liste]] ordonnée de [[Fraction (mathématiques)|fractions]], et d'un nombre entier <math>N_0</math> de départ. Le programme produit une [[suite d'entiers]] <math>N_p</math>, définie par la procédure suivante :
# Initialiser l'examen avec la première fraction <math>F</math> de la liste ;
# Si la multiplication <math>F\times N_p</math> donne un entier, cet entier sera (par définition) <math>N_{p+1}</math> (et réinitialiser l'examen en 1 pour trouver son successeur) ;
# Sinon, si la liste des fractions n'est pas épuisée, poursuivre l'examen avec la fraction suivante (et reprendre l'examen en 2) ;
# Sinon la procédure s'arrête (et la suite résultante est alors finie).

=== Exemple ===

Considérons le programme FRACTRAN correspondant à la liste de fractions <math>\left( \frac 3{10},  \frac 43 \right)</math> . 

Si on l'applique à l'entier 14, comme ni <math>\frac 3{10} \times 14</math>,  ni <math>\frac 43 \times 14</math> ne sont des entiers, le programme s'arrête immédiatement.

Si on l'applique à l'entier 15, on obtient successivement 20 (car seul <math>\frac 43 \times 15</math> est un entier), puis 6 (car <math>\frac {3}{10} \times 20</math> est un entier) , puis 8 (car seul <math>\frac 43 \times 6</math> donne un entier), puis la procédure s'arrête.

=== Principe ===

Le principe s'appuie sur l'existence d'une [[Théorème fondamental de l'arithmétique|décomposition en produit de facteurs premiers]] des entiers, et sur la notion de [[valuation#Valuation p-adique|valuation p-adique]].

Tout entier ''A'' possède une décomposition en produit de facteurs premiers unique, dans laquelle l'exposant du nombre premier ''p'' est appelé '''valuation de ''p'' dans ''A''''', et est noté <math>v_p(A)</math>. Pour un entier ''A'' donné, les <math>v_p(A)</math> sont tous nuls, sauf un nombre fini d'entre eux.

Un programme FRACTRAN peut être vu comme fonctionnant sur une machine disposant d'une infinité de registres, chaque registre contenant un nombre entier. L'état de la machine est alors donné par le [[codage de Gödel]], où les registres successifs représentent l'exposant des nombres premiers successifs. Par exemple, l'état 60 est donné par sa décomposition en facteurs premiers :
:<math display="block">60 = 2^2 \times 3^1 \times 5^1</math>
Il représente l'état où le premier registre (celui de 2) contient la valeur 2, le second (celui de 3) contient la valeur 1, le troisième (celui de 5) contient la valeur 1, et tous les autres registres sont à zéro. Ou encore, en termes de valuation, v2=2, v3=1 et v5=1.

Multiplier l'entier ''A'' par une fraction ''N/D'' permettant d'obtenir un entier ''B'', consiste à opérer, en parallèle sur l'ensemble des ''p'', des additions et des soustractions sur les <math>v_p</math> : la valuation de ''p'' dans ''A'' est augmentée de celle de ''p'' dans ''N'', ou diminuée de celle de ''p'' dans ''D''.

=== Analyse de l'exemple ===

Ainsi, la liste précédente (3/10, 4/3) n'opère que sur les valuations de 2, 3 et 5, qui sont les seuls facteurs premiers présents dans les deux fractions :
* La première fraction (<math>3/10=2^{-1}.3^1.5^{-1}</math>) enlève 1 aux valuations de 2 et 5, lorsque cela est possible, et dans ce cas augmente de 1 la valuation de 3. Cette première fraction agit donc tant que les valuations de 2 et de 5 sont strictement positives.
* La seconde fraction (<math>4/3=2^{2}.3^{-1}.5^{0}</math>) ne prend le relais que lorsque la première ne peut plus opérer, c'est-à-dire quand la valuation de 2 ou de 5 est nulle. Dans ce cas, elle augmente la valuation de 2 de deux unités, et baisse celle de 3 d'une unité.
Lorsque ''A'' s'écrit <math>2^a \times 3^b \times 5^c\times...</math> (multiplié par un facteur ''A’'' quelconque premier avec 30),
* si <math>a = b = 0</math> aucune des deux fractions ne peut s'appliquer et le programme s'arrête,  la valeur restant inchangée
* sinon
** si <math>c \le a</math>, avec la première fraction la procédure transforme ''A'' en <math>B=2^{a-c} \times 3^{b+c}\times...</math>, puis avec la seconde fraction transforme le résultat en <math>2^{a+2b+c} \times...</math>, et la procédure s'arrête.
** si <math>a < c</math>, le comportement de la suite est plus complexe :
*** La première fraction donnera <math>B=3^{b+a} \times 5^{c-a}\times...</math> ;
*** la seconde fraction prend le relais et transforme le résultat en <math>2^{2} \times3^{b+a-1}\times5^{c-a}\times...</math>. On peut alors appliquer à nouveau la première fraction pour obtenir <math>2^{1} \times3^{b+a}\times5^{c-a-1}\times...</math>. Ces deux actions ont ainsi augmenté de 1 l'exposant de 2, laissé inchangé celui de 3 et diminué celui de 5
***  ... et ainsi de suite, les fractions alternant leur transformation jusqu'à ce que l'exposant de 5 soit nul.
*** La procédure s'arrête au nombre  <math>2^{a+2b+c} \times 3^0\times 5^0 \times...</math> 

Le « programme » que constitue la liste des fractions permet ainsi de définir des opérations sur les valuations.

== Opérations basiques ==

=== Addition ===

La liste contenant l'unique fraction <math>\frac32=2^{-1}\times3^1</math> permet de faire la somme des valuations de 2 et de 3 : lorsque A s'écrit <math>2^a \times 3^b \times...</math>,  la procédure s'applique jusqu'à ce que A soit transformé en <math>3^{a+b} \times...</math>.

=== Soustraction ===

La simple fraction <math>\frac 16</math> permet de transformer le nombre <math>2^a3^b</math> en 
* <math>2^{a-b} 3^0</math> , si <math>a > b</math> ;
* <math>2^0 3^{b-a}</math>, si <math>b > a</math> ;
* <math>2^0 3^0</math> si <math>a = b</math>.

=== Boucle infinie ===

Les exemples précédents donnent des séries finies, mais ce n'est pas nécessairement le cas. Un programme simple comme (2/3 ; 3/2) appliqué à n'importe quel nombre d'entrée commencera dans un premier temps par transférer la valuation de 3 en l'additionnant à celle de 2.

À ce stade, si l'une ou l'autre des valuations n'est pas nulle au départ, le programme bouclera :
* Le registre des 3 étant épuisé, le programme ne peut appliquer [2/3] et appliquera [3/2], déplaçant une unité du registre des deux vers celui des 3.
* L'étape suivante, le registre des 3 contenant une unité, [2/3] s'appliquera en priorité, transférant l'unité en sens inverse.
Ce système de bouclage est cependant très utile pour gérer des boucles de programmes grâce à des couples d'indicateurs d'états, comme le montre l'exemple suivant de la multiplication.

=== Transfert d'un nombre ===

Le transfert d'un nombre d'un registre à l'autre s'effectue comme une addition.

Par exemple, le transfert du registre des 2 (v2) vers celui des 3 (v3) s'effectuera par la réitération de l'opération (3/2) sur le nombre <math> 2^a\times 3^0\times \cdots </math>

Deux points importants sont à noter pour de telles opérations :
* Un transfert ne se fait (généralement) pas en une opération unique, mais constitue souvent une étape dans un programme. De ce fait, il faut garder en tête que sans autres précautions, la procédure permet que d'autres opérations sont susceptibles de s'intercaler pendant un transfert, lesquelles peuvent modifier ou compromettre le résultat.
* Bien entendu, pour leur bon fonctionnement, ces opérations supposent que le registre d'accueil ou intermédiaire est initialement à zéro. Cette condition est normalement assurée en imposant des conditions au nombre <math>N_0</math> de départ.

=== Duplication et indicateurs d'états ===
Il est aisé de dupliquer la valeur {{mvar|a}} du registre v2 en la  transférant dans v3 et v5 grâce à la fraction 15/2 mais cela détruit la valeur a du registre v2 qui devient seulement un registre de décompte<ref>{{lien web|url=https://wiki.xxiivv.com/site/fractran.html |langue=en|titre=Fractran is based on one of the most bizarrely elegant concepts of computation.}}</ref>.

Si l'on cherche à conserver la valeur {{mvar|a}} dans v2, il faut utiliser un autre registre de décompte, par exemple le registre v5 en y transférant la valeur {{mvar|a}} (multiplication par 5/2) '''puis''' transférer la valeur de v5 dans v2 et v3 (multiplication par 6/5). Cette notion d'actions successives nécessite d'indiquer au programme quelle étape il doit effectuer (transfert de v2 dans v5 ou transfert de v5 dans v2 et v3). Dans le cas présent il ne faut pas qu'il retourne à la première étape quand celle-ci est terminée. Cela nécessite deux autres registres v7 et v11 dits '''indicateurs d'[[état (informatique)|état]]s'''.
* v7, mis à 1 en début de programme, sert à indiquer que l'on est dans l'étape 1. Pour effectuer le transfert de v2 vers 5,  en multipliant par 5/14, on serait sûr que le transfert ne s'effectue que si v7 est à 1 mais ce test est destructif car v7 passe à zéro.
* Il est donc nécessaire d'utiliser un registre supplémentaire v11 pour signifier que l'on est encore dans l'étape 1. On multiplie alors, non pas par 5/2, ni 5/14 mais par 55/14. Le registre d'états v7 passe à 0 mais le registre d'états v11 passe à 1. Au passage suivant, le programme ne peut plus effectuer l'action 55/14, mais si la seconde fraction du programme est 7/11, celle-ci remet le registre v7 à 1 et v11 à 0 et on peut continuer le transfert jusqu'à ce que le registre v2 soit vide.
* A ce stade là, v2 et v3 sont vides, v5 est plein, v7 est à 1 et v11 à 0. Le programme ne peut effectuer ni 55/14, ni 7/11, il est temps de passer à l'étape 2 en mettant définitivement v7 à 0 par la fraction 1/7.
* le programme se termine par la fraction 6/5, qui, ne touchant ni à v7 ni à v11 empêche l'application des trois premières fractions
Le programme <math>\left(\frac{55}{14}, \frac{7}{11}, \frac{1}{7},\frac{6}{5}\right)</math> transforme alors <math>2^a\times 3^0\times 5^0\times 7^1\times11^0\times \cdots</math> en <math>2^a\times 3^a\times 5^0\times 7^0\times11^0\times \cdots</math>

Pour la multiplication décrite ci-après, par exemple, le transfert du produit des registres des 2 et des 3 vers celui des 5 nécessite l'utilisation d'un registre supplémentaire (assigné à celui des 7), pour réaliser des duplications, et deux autres (ceux des 11 et 13), pour réaliser un indicateur d'états.

=== Multiplication ===

On peut créer une [[fonction multiplicative]] à l'aide d'une boucle additive. L'idée centrale d'un tel algorithme est que partant d'un résultat nul, calculer <math>a\times b</math> consiste à additionner <math>a</math> fois la valeur <math>b</math> au résultat.
Cet algorithme s'applique à un nombre <math>2^a 3^b</math> et le transforme en <math>5^{ab}</math>.

En termes de registres, on peut coder <math>a</math> par v2, <math>b</math> par v3 et le résultat par v5. Fondamentalement, l'opération consiste à additionner v3 à v5, et répéter l'opération v2 fois.

;Restauration du registre v3
Comme l'addition de v3 à v5 « consomme » la valeur de v3, il nous faudra également un registre v7 pour mémoriser cette valeur et la restaurer d'une addition à l'autre. En notant les fractions qui réalisent les différents transferts, l'algorithme devient :
* [ 1/2 ] Si v2 n'est pas nul, le décrémenter (pour compter un passage) ;
* [ 5x7 / 3 ] Une boucle intérieure ajoute v3 à v5, et en parallèle, recopie aussi v3 en v7 (ce faisant, en mettant v3 à zéro) ;
* [ 3/7 ] Quand la boucle intérieure est terminée (v3 est nul), on remet v3 la valeur initiale (présente dans v7, ce faisant, mettant v7 à zéro).
* Puis on recommence (tant que v2 n'est pas nul).

;États successifs de l'algorithme
Cependant, on voit que la règle disant que les fractions sont examinées dans un ordre fixe ne permet pas simplement de recopier d'un côté v3 en v7, puis v7 en v3. La présence simultanée d'un facteur [7/3] et d'un facteur [3/7] dans la liste risque d'engendrer le même type de [[boucle infinie]] que précédemment. Suivant la fraction rencontrée en premier, l'une des opérations sera prioritaire sur l'autre, et l'un ou l'autre de ces deux registre ne pourra pas être vidé jusqu'au bout.

Pour retenir l'une des actions tant que l'autre n'est pas terminée, il faut introduire la notion d'[[État (informatique)|état]] dans l'algorithme, et distinguer entre un état ''A'', où v7 est transféré vers v3 pour le réinitialiser, et un état ''B'', où l'addition de v3 à v5 est réalisée tout en transférant v3 à v7. L'algorithme devient :

{| class="wikitable"
|-
! scope=col | État courant
! scope=col | Étape
! scope=col | Condition
! scope=col | Action élémentaire
! scope=col | Opérateur
! scope=col | État suivant
|-
| rowspan="4" align="center" | A
| Réinitialisation : transférer v7 à v3
| v7 > 0
| Soustraire1 à  v7<br>ajouter 1 à v3
| align="center" | 3/7
| align="center" | A
|-
| Si v2 positif, décrément<br>et entrée en boucle B
| v7 = 0 et<br>v2 > 0
| Soustraire 1 à v2
| align="center" | 1/2
| align="center" | B
|-
| Vider v3
| v7 = 0 et<br>v2 = 0 et<br>v3 > 0
| Soustraire 1 à v3
| align="center" | 1/3
| align="center" | A
|-
| Fin du programme
| v7 = 0 et<br>v2 = 0 et<br>v3 = 0
| Stop<br>(résultat dans v5)
| align="center" | ∅
| align="center" | ∅
|-
| rowspan="2" align="center" | B
| Ajouter v3 à v5 et v7
| v3 > 0
| Soustraire 1 à v3<br>Ajouter 1 à v5<br>Ajouter  1 à v7
| align="center" | 5*7 / 3
| align="center" | B
|-
| Réinitialiser
| v3 = 0
| Rien
| align="center" | A
|}

;Indicateurs d'état couplés
Pour gérer ces états, de nouvelles variables sont nécessaires : elles jouent le rôle d''''indicateurs d'états'''. L'idée de base est que si la valeur d'un indicateur (v11) est nulle dans l'état courant, toute fraction présentant cet indicateur au dénominateur ne pourra pas être exécutée. Cependant, deux indicateurs d'états sont nécessaires pour la seule boucle B : en effet, le premier indicateur (v11) étant consommé par le test, il est nécessaire d'en posséder un second (v13) pour indiquer au programme qu'il doit continuer dans le même état.

Les indicateurs d'état pour la boucle B seront donc v11 et v13.
* Tant que ces deux indicateurs sont nuls, les fractions de la boucle B (qui doivent donc être examinées en premier) ne peuvent pas s'exécuter, et les fractions de l'état A (qui sont examinées ensuite) sont exécutées.
* [ 3/7 ] v7 est retranscrit dans v3.
* [ 11/2 ] v2 décrémenté d'une unité, et v11 est positionné à 1, permettant l'exécution des éléments de la boucle B.
* [ (5.7.13) / (3.11) ] v3 est additionné à v5 et transféré à v7, si v11 le permet. Mais ce test « consommant » v11, il faut dupliquer provisoirement l'information dans v13.
* [ 11/13 ] L'indicateur v13 est ensuite retransféré en v11, permettant de répéter la boucle B. La présence simultanée des facteurs 11/13 et 13/11 créé une boucle dans l'état B, mais cette boucle n'est pas infinie, parce que v3 finit par s'annuler.
* [ 1/11 ] Quand le transfert est achevé,  la boucle B doit s'interdire d'intervenir tant que la main est à l'état A, en repositionnant v11 à zéro.

En fin de compte, l'algorithme travaille sur les valuations de 2, 3, 5 mais aussi 7, 11 et 13.
En ajoutant les indicateurs d'états et les instructions associées au tableau d'algorithme de la multiplication, on obtient :

{| class="wikitable"
|-
! scope=col | Instruction<br>FRACTRAN
! scope=col | État courant
! scope=col | Indicateurs<br>d'état
! scope=col | Condition
! scope=col | Action
! scope=col | État suivant
|-
| align="center" | <math>\frac{3}{7}</math>
| rowspan="4" align="center" | A
| rowspan="4" | Aucun
| v7 > 0
| Soustraire  1 à v7<br>Ajouter 1 à v3
| align="center" | A
|-
| align="center" | <math>\frac{11}{2}</math>
| v7 = 0 et<br>v2 > 0
| Soustraire 1 à v2<br>Mettre v11 à 1
| align="center" | B
|-
| align="center" | <math>\frac{1}{3}</math>
| v7 = 0 et<br>v2 = 0 et<br>v3 > 0
| Soustraire 1 à v3
| align="center" | A
|-
|
| v7 = 0 et<br>v2 = 0 et<br>v3 = 0
| Stop
|
|-
| align="center" | <math>\frac{5 \cdot 7 \cdot 13}{3 \cdot 11}, \frac{11}{13}</math>
| rowspan="2" align="center" | B
| rowspan="2" | v11, v13
| v3 > 0
| Soustraire 1 à  v3<br>Ajouter 1 à v5<br>Ajouter 1 à v7
| align="center" | B
|-
| align="center" | <math>\frac{1}{11}</math>
| v3 = 0
| Mettre v11 à 0
| align="center" | A
|}

Quand on écrit la liste d'instructions FRACTRAN, on doit mettre les instructions de l'état A en dernier, car l'état A n'a pas d'indicateur d'état, c'est l'état par défaut. Tous les autres états, en effet (un seul dans cet exemple) sont protégés en exécution par leurs indicateurs d'état.

Ainsi le programme FRACTRAN de multiplication est la liste suivante :


:<math>\left( \frac{455}{33}, \frac{11}{13}, \frac{1}{11}, \frac{3}{7}, \frac{11}{2}, \frac{1}{3} \right)</math>

Si on entre le nombre <math>2^a3^b</math>, le programme rend <math>5^{ab}</math><ref group=note>{{en}} Des algorithmes similaires sont décrits dans [http://www.esolangs.org/wiki/Fractran cette page].</ref>.

[[Fichier:FRACTRANmult0.gif|thumb|center|544px|Simulation de la machine FRACTRAN ci-dessus lors du calcul de 3×2, donc en entrant 2<sup>3</sup>×3<sup>2</sup>=72, et en récupérant à la fin 5<sup>6</sup>.]]

=== Division euclidienne ===
La [[division euclidienne]] de ''a'' par ''b'' (''a'' et ''b'' entiers naturels, ''b'' > 1) est la donnée de deux entiers naturels ''q'' et ''r'' tels que ''r'' < ''b'' et ''a = bq + r''. Cette division euclidienne peut être vue comme une boucle de soustractions : diviser ''a'' par ''b'', c'est ôter ''b'' à ''a'' autant de fois qu'il est nécessaire, le nombre de fois où cette [[soustraction]] est effectuée correspond à ''q'', la dernière valeur dans ''a'' correspond au reste.

L'algorithme travaille lors sur v2 contenant ''a'', v3 contenant ''b'', v5 destiné à contenir ''q'', et v7 destiné à contenir ''r''. Ces variables sont complétées par 4 indicateurs d'états v11, v13, v17, v19. 

Le programme FRACTRAN qui suit consiste en trois états :
* l'état A opère différemment selon que v3 est plus petit ou plus grand que v2;
** si  v3 ≤ v2,  la boucle retranche v3 à v2, vide v3 dans v7,  ajoute 1 à v5 et passe à l'état B ;
** si  v3 > v2, la boucle vide v2 dans v7 et passe à l'état X.
* l'état B est une sur-boucle qui ré-effectue la boucle A après avoir au préalable vidé v7 dans v3;
* l'état X consiste à vider v3 quand v2 est vide et v3 est non vide.

{| class="wikitable"
|-
! scope=col | Instructions <br>FRACTRAN
! scope=col | État courant
! scope=col | Indicateurs<br>d'état
! scope=col | Conditions
! scope=col | Actions
! scope=col | État suivant
|-
| align="center" | <math>\frac{7 \cdot 13}{2 \cdot 3 \cdot 11}, \frac{11}{13}</math>
| rowspan="3" align="center" | A
| rowspan="3" | v11, v13
| v2 > 0 et<br>v3 > 0
| Soustraire 1 à v2<br>Soustraire 1 à v3<br>Ajouter  1 à v7
| align="center" | A
|-
| align="center" | <math>\frac{1}{3 \cdot 11}</math>
| v2 = 0 et<br>v3 > 0
| Soustraire 1 à v3<br>Mettre v11 à 0
| align="center" | X
|-
| align="center" | <math>\frac{5 \cdot 17}{11}</math>
| v3 = 0
| Ajouter 1 à v5<br>Mettre v11 à 0<br> Mettre v17 à 1
| align="center" | B
|-
| align="center" | <math>\frac{3 \cdot 19}{7 \cdot 17}, \frac{17}{19}</math>
| rowspan="2" align="center" | B
| rowspan="2" | v17, v19
| v7 > 0
| Soustraire 1 à v7<br>Ajouter 1 à v3
| align="center" | B
|-
| align="center" | <math>\frac{11}{17}</math>
| v7 = 0
| Mettre v11 à 1<br> Mettre v17 à 0
| align="center" | A
|-
| align="center" | <math>\frac{1}{3}</math>
| rowspan="2" align="center" | X
| rowspan="2" |
| v3 > 0
| Soustraire 1 à v3
| align="center" | X
|-
| 
| v3 = 0
| Stop
| 
|}

L'écriture du programme est alors :

:<math>\left( \frac{91}{66}, \frac{11}{13}, \frac{1}{33}, \frac{85}{11}, \frac{57}{119}, \frac{17}{19}, \frac{11}{17}, \frac{1}{3} \right)</math>

Il suffit d'entrer <math>2^a 3^b 11</math> pour obtenir en sortie <math>5^q 7^r</math> où <math>a = bq + r</math> avec <math>0 \le r < d</math>.

== Génération de suites ==
Certains programmes bouclent indéfiniment, et génèrent des suites infinies qui peuvent avoir des propriétés intéressantes.
=== Algorithme de Conway des nombres premiers ===
Le programme suivant est présenté par John Conway dans le livre coécrit avec Richard Guy ''{{Langue|en|The Book of Numbers}}''. John Conway les appelle {{Citation|les 14 fractions fantastiques}} (''Fourteen Fantastic Fractions'')<ref name="HavilHisto"/>.

:<math>\left( \frac{17}{91}, \frac{78}{85}, \frac{19}{51}, \frac{23}{38}, \frac{29}{33}, \frac{77}{29}, \frac{95}{23}, \frac{77}{19}, \frac{1}{17}, \frac{11}{13}, \frac{13}{11}, \frac{15}{14}, \frac{15}{2}, \frac{55}{1} \right)</math>

Ce programme, appliqué à l'entier 2, génère une suite qui contient tous les termes de la forme <math>2^p</math> où <math>p</math> est un [[nombre premier]]. Réciproquement, toute [[Puissance de deux|puissance de 2]] dans cette suite a pour exposant 1 ou un nombre premier. Cette suite porte le nom de ''{{Langue|en|Conway primegame}}''<ref>Voir {{OEIS|id=A007542}}.</ref>.

L'algorithme est essentiellement un algorithme de division euclidienne. Le principe est le suivant : partant d'un nombre de la forme <math>2^n 7^m</math> où 0 ≤ ''m''  < ''n'', l'algorithme tente de diviser ''n''+1 par tous les nombres de ''n'' à 1, jusqu'à ce qu'il trouve le plus grand entier ''k'' tel que ''k'' divise ''n''+1 et retourne alors <math>2^{n+1} 7^{k-1}</math>. Les seuls cas où l'algorithme rend une puissance de 2 sont les cas où ''k'' = 1, c'est-à-dire les cas où ''n''+1 est premier<ref group="note">Pour une explication détaillée, voir Julian Havil, ''{{Langue|en|Nonplussed!: Mathematical Proof of Implausible Ideas}}'', {{Langue|en|Princeton University Press}}, 2007, {{ISBN|978-0691120560}}.</ref>.

=== Suite de Fibonacci ===

Le programme suivant :

:<math>\left( \frac{23}{95}, \frac{57}{23}, \frac{17}{39}, \frac{130}{17}, \frac{11}{14}, \frac{35}{11}, \frac{19}{13}, \frac{1}{19}, \frac{35}{2}, \frac{13}{7}, 7 \right)</math>

appliqué à l'entier 3, génère une suite qui contient tous les termes de la forme <math>2^a 3^b</math> où a et b sont deux termes consécutifs de la [[suite de Fibonacci]]. Réciproquement, tout terme de la suite de la forme <math>2^a 3^b</math> a pour exposant deux termes consécutifs de la suite de Fibonacci.

L'algorithme est essentiellement un algorithme d'addition qui consiste, en partant de <math>2^a 3^b</math> à fournir <math>2^b 3^{a+b}</math>. 

{{Boîte déroulante|titre=Démonstration|contenu=
En effet :
* pour <math>a>0</math>, la fraction <math>\frac{35}{2}</math> transforme <math>2^a \times 3^b</math> en <math>5 \times 7 \times 2^{a-1} \times 3^b</math>, puis les fractions <math>\frac{11}{14}</math> et <math>\frac{35}{11}</math> transforment itérativement ce dernier en <math>5^a \times 7 \times 3^b</math>. Dans le cas où <math>a=0</math>, on arrive directement à <math>7 \times 3^b</math> grâce au 7 final de la liste ;
* La fraction <math>\frac{13}{7}</math> transforme alors <math>5^a \times 7 \times 3^b</math> en <math>5^a \times 13 \times 3^b</math>, puis les fractions <math>\frac{17}{39}</math> et <math>\frac{130}{17}</math> le transforment itérativement en <math>5^{a+b} \times 13 \times 2^b</math> ;
* La fraction <math>\frac{19}{13}</math> le transforme en <math>5^{a+b} \times 19 \times 2^b</math>, puis les fractions <math>\frac{23}{95}</math> et <math>\frac{57}{23}</math> le transforment en <math>3^{a+b} \times 19 \times 2^b</math> ;
* Enfin, la fraction <math>\frac{1}{19}</math> supprime le facteur 19.}}

[[File:FRACTRANFibo2.svg|thumb|center|640px|La suite des points <math>(n, x_n)</math> où <math>x_n</math> est le nombre calculé à la ''n''-ème étape, sortis par cette machine FRACTRAN, est assez chaotique (les coordonnées des premiers points sont (0,3), (1,21), (2,39), (3,17), (4,130), (5,190), (6,46), (7,114) et (8,6)…) mais les nombres  <math>x_n</math> n'ayant que 2 et 3 comme facteurs premiers (en rouge) représentent bien les termes successifs de la suite de Fibonacci :

{| class="wikitable centre"
|-
! scope=col | Rang
! scope=col | Nombre
! scope=col | Facteurs premiers
|-
! scope=row | 8
| 6
| <math>2^1\times 3^1</math>
|-
! scope=row | 18
| 18
| <math>2^1\times 3^2</math>
|-
! scope=row | 32
| 108
| <math>2^2\times 3^3</math>
|-
! scope=row | 54
| 1944
| <math>2^3\times 3^5</math>
|}
]]

=== Suite de Syracuse ===

Ce programme présenté par Kenneth G. Monks<ref name="Monks">{{en}} {{pdf}} Kenneth G. Monks, « [http://www.dmtcs.org/pdfpapers/dm050103.pdf {{Langue|en|3x+1 minus the +}}] », in ''{{Langue|en|Discrete Mathematics and Theoretical Computer Science}}'' 5, 2002, 47–54.</ref> :

:<math>\left( \frac{1}{11}, \frac{136}{15}, \frac{5}{17}, \frac{4}{5}, \frac{26}{21}, \frac{7}{13}, \frac{1}{7}, \frac{33}{4}, \frac{5}{2}, 7 \right)</math>

appliqué à <math>2^N</math>, génère une suite qui contient successivement tous les termes <math>2^b</math>, où ''b'' parcourt les termes de la [[Conjecture de Syracuse|suite de Syracuse]] de premier terme N. Réciproquement, toute puissance de 2 dans cette suite a pour exposant un élément de la suite de Syracuse. 

{{Boîte déroulante|titre=Démonstration|contenu=
* Partant de <math>2^N</math>, les fractions <math>\frac{33}{4}</math> et <math>\frac{1}{11}</math> le transforme en <math>3^k \times 2^{N-2k}</math> pour les valeurs croissantes de ''k'' jusqu'à arriver à <math>3^p</math> si N est pair égal à 2''p'', ou bien <math>3^p \times 2</math> si N est impair égal à 2''p''+1.
* Dans le premier cas, le terme final 7 transforme <math>3^p</math> en <math>3^p \times 7</math>, puis les fractions <math>\frac{26}{21}</math> et <math>\frac{7}{13}</math> le transforment itérativement en <math>2^p \times 7</math>. La fraction <math>\frac{1}{7}</math> supprime ensuite le 7 superflu. On est alors passé de <math>2^N</math> à <math>2^{N/2}</math>.
* Dans le deuxième cas, la fraction <math>\frac{5}{2}</math> transforme <math>3^p \times 2</math> en <math>3^p \times 5</math>, puis les fractions <math>\frac{136}{15}</math> et <math>\frac{5}{17}</math> le transforment itérativement en <math>5 \times 2^{3p}</math>. La dernière fraction <math>\frac{4}{5}</math> le transforme enfin en <math>2^{3p+2}</math> qui n'est autre que <math>2^{(3N+1)/2}</math>.
Ainsi, l'exposant N a été modifié en N/2 si N est pair et (3N+1)/2 si N est impair, ce qui est le principe de la suite de Syracuse.
}}

L'idée de Kenneth Monks est d'étudier les suites de Syracuse cycliques en cherchant les propriétés des suites cycliques générées par ce programme<ref name="Monks"/>.

== Programme universel ==
Conway a également défini un programme FRACTRAN universel<ref name="Conway" group="note"/>, constitué des fractions suivantes :
:<math>\left( \frac{583}{559},\frac{629}{551},\frac{437}{527},\frac{82}{517},\frac{615}{329},\frac{371}{129},\frac{1}{115},\frac{53}{86},\frac{43}{53},\frac{23}{47},\frac{341}{46},\frac{41}{43},\frac{47}{41},\frac{29}{37},\frac{37}{31},\frac{37}{31},\frac{299}{29},\frac{47}{23},\frac{161}{15},\frac{527}{19},\frac{159}{7},\frac{1}{17},\frac{1}{13},\frac{1}{3} \right)</math>
On peut alors montrer que, pour toute [[Fonction semi-calculable|fonction partielle récursive]] ''f'', il existe un entier ''c'' tel que, pour tout entier ''n'', en appliquant le programme FRACTRAN avec la liste ci-dessus au nombre <math>c \times 2^{2^n}</math>, on atteint le nombre <math>2^{2^{f(n)}}</math> si et seulement si le calcul de ''f''(''n'') se termine. Cette propriété montre qu'on obtient en FRACTRAN toutes les fonctions calculables, et en particulier que la question de l'arrêt d'un programme FRACTRAN est indécidable en général, car se ramenant au [[problème de l'arrêt]]. 

== Notes et références ==
=== Notes ===
<references group="note"/>

=== Références ===
<references/>
{{Traduction/Référence|en|FRACTRAN|394521074}}

== Voir aussi ==
=== Articles connexes ===
* [[Nombre premier]]
* [[Liste de nombres premiers]]

=== Ressources bibliographiques ===
* John Conway, « {{Langue|en|FRACTRAN: A simple universal programming language for arithmetic}} », in ''{{Langue|en|Open Problems in Communication and Computation}}'', Thomas M. Cover (relecteur), B. Gopinath (relecteur), Springer ; {{1re}}{{éd.}} ({{date-|9 novembre 1987}}) ;
* Julian Havil, ''{{Langue|en|Nonplussed!: Mathematical Proof of Implausible Ideas}}'', [[Princeton University Press]], 2007 ;
* Kenneth G. Monks, « [http://www.dmtcs.org/pdfpapers/dm050103.pdf {{Langue|en|3x+1 minus the +}}] », in ''{{Langue|en|Discrete Mathematics and Theoretical Computer Science}}'' 5, 2002, 47–54.

{{Palette|Langage de programmation exotique}}
{{Portail|informatique théorique|mathématiques|programmation informatique}}

[[Catégorie:Langage de programmation exotique]]
[[Catégorie:John Horton Conway]]