| Dans l'état | Lit | Écrit | Se déplace | État suivant |
|---|
Simulateur de machine de Turing
Une machine de Turing est l'ordinateur le plus simple possible : une tête qui lit un symbole d'un ruban infini, écrit un symbole, se déplace d'une case vers la gauche ou la droite et change d'état, en suivant une courte table de règles. Alan Turing l'a inventée en 1936, et tout ce que fait votre ordinateur pourrait en principe se faire ainsi. Écrivez vos propres règles ou chargez un exemple, appuyez sur Exécuter et regardez le ruban changer étape par étape, avec en dessous un diagramme de tout son historique. Choisissez un programme ou écrivez le vôtre, saisissez l'entrée et appuyez sur Exécuter, ou sur Pas à pas pour suivre une règle à la fois ; Retour annule une étape. Chaque ligne du programme est une règle : état, symbole lu, symbole à écrire, déplacement (L, R ou N pour aucun déplacement) et état suivant, par exemple A 0 -> 1 R B. Utilisez _ pour une case vide. La machine démarre dans l'état de la première règle, sur le premier symbole de l'entrée, et s'arrête dans H, accept ou reject, ou lorsqu'aucune règle ne s'applique. Le diagramme montre le ruban après chaque étape, de haut en bas.
Comment ça marche
- Choisissez un programme d'exemple ou écrivez des règles comme A 0 -> 1 R B, une par ligne, et saisissez l'entrée.
- Appuyez sur Exécuter pour voir la tête se déplacer, ou sur Pas à pas pour suivre une règle à la fois ; Retour annule une étape.
- Lisez l'état, les étapes et les symboles sur le ruban dans les tuiles, et l'historique du ruban dans le diagramme.
Comment fonctionne la machine
À chaque instant, la machine se trouve dans l'un de quelques états et sa tête est posée sur une case du ruban. La règle correspondant à cet état et au symbole sous la tête dit trois choses : quel symbole écrire dans la case, s'il faut se déplacer à gauche, à droite ou pas du tout, et dans quel état passer ensuite. C'est toute la machine. Elle s'arrête lorsqu'elle atteint un état d'arrêt, comme H, accept ou reject, ou lorsqu'aucune règle ne s'applique. Un programme qui ajoute 1 à un nombre binaire n'a besoin que de neuf règles de ce genre.
Castors affairés
Quelle machine à n états, démarrée sur un ruban vide, écrit le plus de 1 avant de s'arrêter ? Tibor Radó a posé la question en 1962. Les machines championnes sont appelées castors affairés, et elles croissent plus vite que toute fonction qu'un ordinateur peut calculer. Deux états donnent 4 uns en 6 étapes, trois états 6 uns, quatre états 13 uns en 107 étapes. La championne à cinq états, trouvée en 1989, écrit 4 098 uns en 47 176 870 étapes, et en 2024 une collaboration en ligne a prouvé, par des mathématiques vérifiées par ordinateur, qu'aucune autre machine à cinq états qui s'arrête ne tourne plus longtemps.
Questions fréquemment posées
Comment écrire une règle ?
Une règle par ligne : l'état actuel, le symbole lu, le symbole à écrire, le déplacement (L, R ou N) et l'état suivant, par exemple A 0 -> 1 R B. La flèche et les virgules sont facultatives. Utilisez _ pour une case vide et # pour un commentaire. La machine démarre dans l'état de la première règle ; un état suivant nommé H ou halt l'arrête, et accept et reject l'arrêtent avec un verdict.
Une machine de Turing peut-elle vraiment tout calculer ?
Tout ce qu'un ordinateur quelconque peut calculer, avec assez de ruban et de temps : c'est la thèse de Church-Turing. Une machine de Turing n'a pas de limite de mémoire, et en ce sens elle est plus puissante que tout ordinateur réel, quoique bien plus lente. Ce qu'elle ne peut pas faire, c'est répondre à toutes les questions : Turing a prouvé qu'aucune machine ne peut décider, pour tout programme et toute entrée, s'il s'arrêtera.
Pourquoi le compteur ne s'arrête-t-il jamais ?
Ses règles ne mènent jamais à un état d'arrêt. Il ajoute sans cesse 1 à un nombre binaire à l'extrémité droite du ruban puis revient en arrière, si bien que le nombre grandit indéfiniment. Le problème de l'arrêt de Turing dit qu'aucune méthode générale ne peut déterminer, pour toute machine, si elle s'arrêtera ; pour ce compteur simple, on le voit, mais pour certaines machines à seulement six états, personne ne le sait encore.
Comment le castor affairé à cinq états peut-il effectuer ici 47 millions d'étapes ?
Le ruban est stocké sous forme de tableau compact qui s'agrandit dans les deux sens, et au réglage Très rapide l'application exécute des centaines de milliers d'étapes entre deux rafraîchissements de l'écran, si bien que l'exécution complète prend quelques secondes dans un navigateur moderne. Le diagramme n'enregistre que les 400 premières étapes, car une image de 47 millions de lignes ne tiendrait sur aucun écran.
Des données sont-elles envoyées à un serveur ?
Non. Le programme s'exécute dans votre navigateur, et votre programme et votre entrée restent dans le stockage local de ce navigateur.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Aller à l'éditeur