Comment la règle 110 de Turing est-elle complète?

J'ai lu la page wikipedia de la règle 110 dans les automates cellulaires, et je sais plus ou moins comment ils fonctionnent (un ensemble de règles décide où tracer le prochain 1 ou 0).

Je viens de lire qu'ils sont complets de Turing, mais je ne peux même pas comprendre comment «programmez-vous» la «règle 110»?

$f$$P$$P$$x$

Les mots cités sont ceux qui doivent être définis. Pour les machines de Turing:

• Un programme est spécifié comme une liste d'états, un alphabet de bande, un état initial, des états finaux et des transitions.
• $T$ $x$$x$$T$
• Une machine de Turing s'arrête si elle atteint un état final. (Il existe quelques variantes ici.)
• Ce que la machine Turing sort (si elle s'arrête), c'est le contenu de la bande.

$S$$P$$x$$S(P,x)$$P$$x$$S(p,x)$$P$$x$

Si vous êtes curieux de la configuration particulière de la règle 110 en tant que système informatique, je vous suggère de jeter un coup d'œil à l'article de Matthew Cook qui prouve l'universalité de la règle 110 (ou plutôt d'un système informatique construit autour de la règle 110).

Quant aux autres règles, telles que la règle 30 et la règle 90, nous ne savons pas qu'elles ne sont pas universelles. Il peut y avoir des systèmes informatiques convaincants construits autour d'eux, ce qui est universel, mais nous n'en sommes tout simplement pas au courant.

D'après la preuve de Matthew:

L'approche adoptée ici n'est pas de concevoir un nouvel automate cellulaire, mais de prendre le plus simple qui présente naturellement un comportement complexe, et de voir si nous pouvons trouver dans ce comportement complexe un moyen de le faire faire ce que nous voulons. Nous ne nous intéresserons pas directement à la table de recherche donnée ci-dessus, mais nous examinerons plutôt le comportement qui se manifeste naturellement par l'action de l'automate au fil du temps.

L'auteur commence par prouver qu'un "système d'étiquettes" qui supprime 2 symboles à chaque étape est universel en compilant un programme de machine de turing à 2 états. Après cela, il prouve qu'un système de planeur peut en effet mettre en œuvre un système de balises. C'est un processus étape par étape. Il étudie ensuite l'espace-temps du CA-110 pour trouver les planeurs et les associer correctement au système de planeurs.

Maintenant, pour votre question: comment «programmez-vous» la «règle 110»?

1. Recherchez la machine de turing à 2 états la plus simple et trouvez les bandes des opérations de base OR, AND, XOR, NOT .

2. Compilez-les dans le système de balises.

3. Compilez l'implémentation du système de balises dans l'implémentation du planeur.

4. Adaptez-le correctement aux planeurs CA-110 et vous avez les opérations de base dans un automate cellulaire.

$1+1=2$

Une note de côté. Les planeurs sont des structures très spéciales. Les opérations seront vues comme des particules se déplaçant et entrant en collision (les planeurs), générant des sorties différentes selon la façon dont ces planeurs partent ou entrent en collision.