Pourquoi FRACTRAN turing est-il complet?

J'ai essayé de rechercher des explications sur Google, mais la plupart des liens ne disent que des choses comme "FRACTRAN est complet. À titre d'exemple, regardons la multiplication."

Je me souviens avoir vu un article du forum xkcd dire que FRACTRAN avait aidé l'affiche à comprendre l'intégralité de Turing. Je cherche une explication intuitive pour expliquer pourquoi cet esolang est Turing complet, car ce n'est pas très évident en regardant la mécanique du langage.

Pour qu'un langage impératif soit complet, il doit avoir:

1. Boucle conditionnelle
2. Nombre arbitraire de variables

FRACTRAN est un langage composé d'une série de fractions qui stockent ses données dans les exposants des nombres premiers.

Disons que vous voulez ajouter deux nombres: 2 ^a 3 ^b devient 5 ^ab

455 11 1 3 11 1
---, -, -, -, -, -
 33 13 11 7 2 3

C'est un programme FRACTRAN pour faire le changement ci-dessus.

Vous commencez avec un nombre comme 72 (2 ³ 3 ² ). Le programme va «en avant» jusqu'à ce qu'il trouve un nombre qui, multiplié par l'instruction, est un autre entier (aucun reste autorisé).

72se poursuivra jusqu'à ce qu'il arrive à 11/2. Il sera alors diviser par le nombre 2et le multiplier par 11(la puissance en 11 est une variable). Cela donne 396. 396est divisible par 33 (en réduisant la puissance 3 et la 11) et multiplié par 455 (en incrémentant 5, 7 et 13 variables). Etc. La description complète de ce programme et son tableau d'état peuvent être lus sur la page wikipedia de FRACTRAN , y compris un très joli gif animé du programme ci-dessus.

D'autres documents FRACTRAN sur Stack Exchange qui touchent à l'exhaustivité de Turing peuvent être trouvés sur: Convert Fractran into Brainfuck (ok, c'est une utilisation vraiment productive de son temps)

La raison pour laquelle Fractran est Turing-complete est qu'il simule une machine de registre. La factorisation principale du nombre stocke le contenu des registres, tandis que la division et la multiplication sont un moyen d'ajouter et de soustraire conditionnellement des registres.

Une partie de l'astuce ici (et cela commence à s'égarer dans la théorie) est que dans les coulisses, il s'agit d'une machine à registre Minsky pour laquelle il a été prouvé que certaines bandes (programmes) sont des machines de Turing SI la bande est représentée comme un nombre Gödel qui est exactement ce que le numéro FRACTRAN est (à partir de la page wikipedia liée):

Gödel a utilisé un système basé sur la factorisation principale. Il a d'abord attribué un nombre naturel unique à chaque symbole de base dans le langage formel de l'arithmétique avec lequel il avait affaire.

Donc, nous avons des boucles conditionnelles, des variables arbitraires stockées sous forme de nombres de Gödel, nous avons une machine de Turing.

Une autre lecture amusante qui touche la Collatz comme la nature de FRACTRAN peut être lue sur Can't Decide? Undecide! qui relient la conjecture de Collatz à FRACTRAN et le problème d'arrêt.

FRACTRAN est un peu difficile à comprendre.

Considérez le programme comme:

LABEL: start
    block1
    block2
    block3
    ...
END

En cela, chaque bloc est de la forme:

IF(registers X >= a, Y >= b)  # or any combination of registers
THEN
    X -= a
    Y -= b

    I += n
    J += m

    goto start

La première déclaration du programme de multiplication ci-dessus:

455
---
 33

Serait écrit sous cette forme:

IF(register `3` >= 1 && `11` >= 1)
THEN
     `3` -= 1
    `11` -= 1

     `5` += 1
     `7` += 1
    `13` += 1

    goto start

Et ainsi, vous pouvez voir clairement le stockage de données et les constructions en boucle nécessaires pour l'exhaustivité de Turing. C'est très rudimentaire, mais il existe et fonctionne comme une simple machine à enregistrer - mais c'est tout ce que vous devez vraiment faire.

Toujours pas convaincu?

Cela emprunte en grande partie à une conférence de Dimitri Hendricks sur les modèles de calcul

Cela prend le programme très simple (2/3)qui est un additionneur (2 ^a 3 ^b -> 3 ^{a + b} ) Mais il est destructeur - la valeur de 2 est effacée dans le cadre du processus.

Permet d'écrire un FRACTRAN de niveau supérieur qui rend facile de ne pas faire une telle destruction.

Le programme original pourrait être considéré comme:

   2
α: - → α
   3

Dans F ₂ , on peut spécifier des «fonctions» d'une sorte.

   10 1
α: - → α, - → β
    3 1

   3
β: - → β
   5 

Pour convertir un programme F ₂ (P) en programme FRACTRAN standard, on fait:

1. P clair des boucles de longueur 1
2. Remplacez les lettres grecques (fonctions) par de nouveaux nombres premiers
3. Remplacez les transitions:

   ace
p: - → q, - → r, - -> s, ...
   bdf

devient:

aq cr es
-, -, -, ...
bp dp fp

Ce que cela a fait, c'est utiliser les nombres premiers p, q, r et s pour stocker l'état du programme.

Et puis nous avons la machine à registres ... elle a un nombre fini de registres qui stockent des nombres arbitraires et deux instructions:

• inc (x _i , m) - incrémente le registre i et passe à la ligne m
• jzdec (x _i , m ₁ , m ₂ ) - si le registre i vaut 0, passez à la ligne m, sinon décrémentez i et passez à la ligne m2.

Il a été démontré que cette machine d'enregistrement est Turing terminée.

Il va ensuite montrer le processus sur plusieurs diapositives de compilation d' un programme machine de registre dans un programme FRACTRAN dans le cadre d'un processus mécanique.

Fondamentalement:

                       pi)
inc (x (i), m) = ---- → m
                        1

                        1 1
jzdec (x (i), m1, m2) = ---- → m2, - → m1
                       p (i) 1

Et donc du fait de l'équivalence entre ces deux modèles de calcul, FRACTRAN est Turing complet.

Btw, si vous voulez vraiment avoir le souffle coupé , lisez Code Golf: Fractran dans lequel certaines personnes ont écrit un programme FRACTRAN pour exécuter un autre programme FRACTRAN.