Machine de Turing sur redstone Minecraft

Construire une machine de Turing avec la redstone dans Minecraft

Une machine de Turing se compose d'une bande infinie divisée en cases, d'une tête de lecture/écriture et d'une table de transition qui fait office de programme. Dans Minecraft, ces composants sont simulés à l'aide de la redstone, un système de transmission de signaux disposant de 16 niveaux de puissance (de 0 à 15). La poussière de redstone transporte un signal sur une distance maximale de 15 blocs, perdant un niveau d'intensité par bloc parcouru.

Composants clés de la redstone :

• Torche : Inverse le signal (porte NON).
• Manette : Fournit une source d'alimentation stable et constante.
• Bouton : Génère une impulsion de durée fixe.
• Répéteur : Amplifie la puissance du signal, impose un flux unidirectionnel et ajoute un délai de 1 à 4 ticks.
• Comparateur : Compare ou soustrait les intensités de signal.

Ces éléments s'assemblent pour former des portes logiques : NON (torche), ET (deux répéteurs alimentant une torche), OU (fils convergents) et NAND/NOR (diverses combinaisons). La machine utilise un alphabet de 4 symboles : 0, 1, vide (ε) et un état réservé.

Cellule mémoire de la bande

Chaque cellule stocke 4 bits (valeurs de 0 à 15) et émet continuellement son signal une fois activée. Par exemple, une cellule peut contenir 0101. Un bouton sur la gauche permet de réinitialiser la cellule. Les bits supplémentaires offrent une marge de manœuvre pour de futures extensions.

La bande complète se compose de 8 cellules de ce type, offrant un total de 32 bits de stockage.

Registre à décalage de la tête

Ce registre suit la position de la tête de lecture/écriture sur la bande. Une lampe allumée indique la cellule active actuelle. Des boutons sur la droite contrôlent le déplacement : gauche, droite et réinitialisation (qui ramène la tête à la lampe la plus à gauche). Une lampe optionnelle à l'extrême gauche signale la fin d'un décalage, ce qui permet de minimiser les retards de synchronisation dans la boucle d'exécution.

Le registre gère les opérations de décalage de bits pour déplacer la tête le long de la bande.

Cellule de programme

Chaque cellule de programme contient 10 bits de données d'instruction :

• 4 bits pour la valeur à écrire.
• 2 bits pour le décalage de la tête (10 = déplacement à gauche, 01 = déplacement à droite).
• 4 bits pour l'état suivant de la machine.

Les opérations suivent une séquence stricte : écriture → décalage → transition d'état. Le programme complet utilise 20 cellules, couvrant 4 états × 4 symboles (y compris ε et l'état d'arrêt).

Convertisseur binaire-décimal

Ce module traduit les adresses binaires en format décimal pour cibler correctement les cellules de la bande. L'entrée se fait par la droite (par exemple, le binaire 10 donne le décimal 2 en sortie à gauche). Cela simplifie l'adressage mémoire.

Cycle d'exécution

Des délais de synchronisation fixes (2 secondes par opération) maintiennent le tout synchronisé sans nécessiter de signaux de fin explicites :

• Lire le symbole de la cellule de bande actuelle.
• Consulter la règle de transition en fonction de l'état et du symbole actuels.
• Écrire la nouvelle valeur issue de la table de transition.
• Déplacer la tête vers la gauche ou la droite.
• Passer à l'état suivant de la machine.
• Si l'état d'arrêt est atteint, stopper ; sinon, répéter le cycle.

Un fil orange relie le module de programme à la boucle d'exécution pour transmettre le signal d'arrêt.

Architecture globale

La construction complète intègre :

• 20 cellules d'instruction de programme.
• 8 cellules mémoire pour la bande.
• Le registre à décalage de la tête.
• Le cycle d'exécution synchronisé.
• Les convertisseurs d'adresses binaire-décimal.

À titre de démonstration pratique, la machine peut incrémenter avec succès un nombre stocké sur la bande.

Points clés à retenir

• La redstone simule fidèlement la logique d'une machine de Turing grâce aux portes standards et aux intensités de signal de 0 à 15.
• Les cellules mémoire de 4 bits intègrent une redondance native pour faciliter l'évolution du montage.
• Les délais fixes simplifient la boucle d'exécution en supprimant le besoin de signaux de retour.
• Un alphabet de 4 symboles et 4 états internes génèrent 20 transitions possibles.
• Le montage est entièrement fonctionnel pour des cas d'usage précis, comme l'incrémentation binaire.

— Editorial Team