Fractran

Le Fractran est un langage de programmation exotique (qui n’a pas été développé dans le but d’être utilisé) inventé par John Conway en 1987. Son nom fait référence au très connu Fortran ( FORmula TRANslator). Le nom FRACTRAN étant la concaténation de FRACtional TRANslator est une référence au FORTRAN.

Un programme FRACTRAN est une liste de fraction prenant en entré un entier positif A et dont le résultat est un entier positif. Cet entier peut être égal à celui entrée dans le cas où aucune solution n’est trouvée. L’entier A est multiplié par toutes les fractions de la liste pour essayer de trouver la première fraction fi de la liste qui multipliée par A donne un entier. Tant que l’on trouve une telle fraction fi, on remplace A par A*fi, qui est un entier, et on répète l’opération. Ainsi si l’entier en sortie est égal à celui en entrée cela signifie qu’aucune multiplication A*fi ne donne un entier. Une image vaut mieux qu’un long discours:

En regardant cette petite animation on peut se demander si un programme Fractran termine forcément. Un programme Fractran peut en effet ne jamais se terminer car si la liste des fractions et l’entier entré sont bien choisis le programme pourra tourner en boucle sans jamais donné un résultat. Un exemple trivial est la liste:

et en entré l’entier 2. On remarque que le programme ne finira jamais.

John Conway a par ailleurs suggéré une liste L permettant de trouver la liste des puissances premières de 2 dans l’ordre croissant. C’est à dire 2³,2⁵, etc .En utilisant la liste L:

les seules puissances de deux qui résulte de ce calcul sont les puissances premières de deux. Ce résultat, bien qu’étonnant, n’est pas très efficace pour trouver ces nombres premiers puisqu’il faut un nombre important d’itérations pour tomber sur ces puissances premières de 2.

Un autre exemple est la suite de fibonacci. Grâce à la liste suivante

et en donnant en entrée 3 on obtiendra la suite de fibonacci avec en sortie

Où a et b sont les deux termes de la suites de fibonacci.

Vous l’aurez compris ce langage n’a pas encore percé mais qui sait, dans un futur proche il pourrait venir concurrencer d’autres langages tel que le python…