- La machine de Turing à 3 états et 3 symboles Bigfoot est un cas où prouver l’arrêt sur un ruban vide nécessite de résoudre un problème de type Collatz, ce qui montre que (BB(3, 3)) pourrait être tout aussi difficile
- Cette machine fait partie des 160 candidats non résolus pour (BB(3, 3)) sur bbchallenge.org, et elle est définie par la table de transitions
1RB2RA1LC_2LC1RB2RB_---2LA1LA - Son comportement se réduit à des règles d’itération sur des configurations (A(a,b,c)) ; selon (b \bmod 6), a augmente ou diminue, et la machine ne s’arrête que lorsque (a) est sur le point de passer sous 0
- Depuis un ruban vide, elle atteint (A(2,1,2)) après 69 étapes ; après 24 millions d’itérations, (a) monte jusqu’à (3,999,888), ce qui rend expérimentalement la probabilité d’arrêt très faible
- La suite (b \bmod 6) est déterministe, mais à grande échelle elle ressemble à une marche aléatoire biaisée vers la droite avec probabilité 2/3 et vers la gauche avec probabilité 1/3 ; pour prouver qu’elle s’exécute indéfiniment, il faudrait montrer que cette fonction de type Collatz n’atteint jamais la transition d’arrêt
Pourquoi Bigfoot rend (BB(3, 3)) difficile
- Prouver l’arrêt d’une seule machine de Turing à 3 états et 3 symboles nécessite de résoudre un problème de type Collatz
- Par conséquent, résoudre le problème (BB(3, 3)) pourrait être aussi difficile que résoudre ce problème de type Collatz
- Paul Erdős a dit à propos des problèmes de type Collatz : « Mathematics may not be ready for such problems »
- Dans un précédent article, Mother of Giants, il était question d’une famille de machines de Turing découvertes lors de la recherche de Busy Beavers « Beeping »
- Pour cette famille, prouver l’existence ou non d’un état de quasi-arrêt (quasihalt) nécessite soit de simuler efficacement un problème de type Collatz, soit de le résoudre complètement
- Bigfoot n’est pas un cas découvert dans une variante du jeu, mais dans le jeu Busy Beaver standard
Cas connus de difficulté pour Busy Beaver
- Plusieurs machines de Turing construites à la main fournissent des cas où prouver certaines valeurs de Busy Beaver nécessiterait de prouver d’autres énoncés mathématiques difficiles
- (BB(745)) : nécessite une preuve de cohérence de ZFC
- (BB(27)) : nécessite une preuve de la conjecture de Goldbach
- (BB(15)) et (BB(5,4)) : nécessitent de prouver la conjecture d’Erdős selon laquelle, pour (n > 8), l’écriture en base 3 de (2^n) contient au moins un chiffre 2
- Cependant, ces valeurs de Busy Beaver sont aujourd’hui hors de portée
- Au cours des 60 dernières années, les seules valeurs prouvées sont (BB(2), BB(3), BB(4), BB(2,3)), et l’on sait que (BB(6) > 10 \uparrow\uparrow 15)
- Avant l’analyse de Bigfoot, on pensait qu’il était possible de prouver (BB(3, 3))
Définition et origine de Bigfoot
- Cette machine de Turing s’appelle Bigfoot, et sa table de transitions est définie par la chaîne suivante
1RB2RA1LC_2LC1RB2RB_---2LA1LA
- C’est une machine répertoriée sur bbchallenge
- Sa table de transitions est la suivante
| État | 0 | 1 | 2 |
|---|---|---|---|
| A | 1RB | 2RA | 1LC |
| B | 2LC | 1RB | 2RB |
| C | — | 2LA | 1LA |
- Bigfoot fait partie des 160 holdouts informels restants pour (BB(3,3)), partagés sur le canal Discord de bbchallenge.org
- Cette machine de Turing précise a été partagée pour la première fois le 14 octobre 2023 par @savask sur le même canal Discord, avec une description de bas niveau de son comportement
- Les analyses ultérieures ont révélé une structure de type Collatz et un caractère de marche aléatoire biaisée
Un comportement qui se réduit à des configurations (A(a,b,c))
- Posons la configuration générale comme suit
[ A(a, b, c) = 0^\infty ; 12^a ; 11^b ; \text{ <A } ; 11^c ; 0^\infty ]
- Lorsque Bigfoot entre dans une configuration (A(a,b,c)) avec (c \ge 1), les règles ci-dessous décrivent exactement la suite de son comportement, jusqu’à l’arrêt ou pour toujours
[ \begin{array}{l} A(a, 6k, c) \to A(a, 8k+c-1, 2) \quad \text{if } 8k+c \ge 1 \ A(a, 6k+1, c) \to A(a+1, 8k+c-1, 3) \quad \text{if } 8k+c \ge 1 \ A(a, 6k+2, c) \to A(a-1, 8k+c+3, 2) \quad \text{if } a \ge 1 \ A(a, 6k+3, c) \to A(a, 8k+c+1, 5) \ A(a, 6k+4, c) \to A(a+1, 8k+c+3, 2) \ A(a, 6k+5, c) \to A(a, 8k+c+5, 3) \end{array} ]
[ A(0, 6k+2, c) \to \text{Halt}(16k+2c+7) ]
- Ces règles itèrent une fonction de type Collatz sur les paramètres (b) et (c)
- (a) évolue comme une valeur cumulée
- Si (b \equiv 1 \pmod{6}) ou (b \equiv 4 \pmod{6}), alors (a) augmente
- Si (b \equiv 2 \pmod{6}), alors (a) diminue
- Bigfoot ne s’arrête que lorsque (a) est sur le point de descendre sous 0
Trajectoire observée à partir d’un ruban vide
- En partant d’un ruban vide, Bigfoot atteint la configuration (A(2,1,2)) après 69 étapes
- Dans les simulations qui suivent, (a) semble augmenter régulièrement ; après 24 millions d’itérations, on obtient (a = 3,999,888)
- Si l’on suppose que la suite des restes (b \bmod 6) est uniformément aléatoire, ce processus est équivalent à une marche aléatoire biaisée sur la droite numérique
- À chaque étape, la probabilité d’aller vers la droite est (\frac{2}{3})
- La probabilité d’aller vers la gauche est (\frac{1}{3})
- La théorie des chaînes de Markov permet de prouver que, lorsque la position courante est (a=n), la probabilité d’atteindre (a=-1) à l’avenir est ((\frac{1}{2})^{n+1})
- En réalité, la suite (b \bmod 6) n’est pas aléatoire mais entièrement déterministe, et suit systématiquement un motif impair·impair·pair·pair
- Malgré cela, à grande échelle, sa trajectoire ressemble à celle d’une chaîne de Markov aléatoire
- Après 24 millions d’étapes, on s’attendrait à ce que la chaîne de Markov se soit déplacée 8 millions de fois vers la droite et 4 millions de fois vers la gauche
- C’est très proche de la valeur réelle de (a), autour de 4 millions
L’heuristique selon laquelle elle ne s’arrête « probviously » pas
- Lorsque (a \approx 4,000,000), la probabilité qu’une chaîne de Markov aléatoire atteigne (a=-1) est d’environ ((\frac{1}{2})^{4,000,000})
- Ce nombre est si petit que, scientifiquement, on le traite comme un échec garanti
- Si Bigfoot se comporte comme une chaîne de Markov, il semble qu’elle ne s’arrêtera pas
- Mais il s’agit d’une heuristique expérimentale, pas d’un théorème mathématique rigoureux
- On ne peut pas exclure que Bigfoot s’arrête après un googolplex d’itérations
- John Conway a forgé l’expression « probviously » pour décrire l’heuristique selon laquelle la conjecture de Collatz serait « probviously » vraie, mais aucune preuve de Collatz n’est encore en vue
Les deux issues possibles pour Bigfoot
- Bigfoot est dans l’un des deux cas suivants
- Elle s’arrête
- Elle s’exécute indéfiniment
- Si elle s’arrête, on peut le prouver en accélérant suffisamment l’itération de la fonction de type Collatz et en simulant jusqu’au bout
- Si elle s’exécute indéfiniment, il faut prouver que cette fonction de type Collatz n’atteint jamais la transition d’arrêt avec (a=0)
- Selon l’heuristique des chaînes de Markov, le second cas semble plus plausible, et il paraît beaucoup plus difficile à prouver
Le nom Cryptids
- Les machines de ce genre ont un comportement qui peut se réduire à des règles mathématiques relativement simples, mais ces règles appartiennent à une classe de problèmes mathématiques ouverts
- Elles ressemblent à des créatures légendaires dont on dit qu’elles s’arrêtent ou ne s’arrêtent pas, sans que personne puisse apporter de preuve concrète dans un sens ou dans l’autre
- Il a été proposé d’appeler ces machines Cryptids
- L’analogie est celle de créatures légendaires comme le monstre du Loch Ness ou le Chupacabra
- Cette machine de Turing a reçu le nom Bigfoot parce qu’elle semble marcher au hasard
Ce comportement de type Collatz est-il vraiment difficile ?
- La dynamique de cette fonction de type Collatz particulière semble avoir été très peu analysée auparavant
- Avec un peu de théorie des nombres et de calcul, il reste possible de trouver une propriété mathématique astucieuse qui s’applique spécifiquement à ce problème
- Si une telle propriété est découverte, cela montrerait que la preuve de (BB(3,3)) reste encore à portée
- Les questions que l’on peut poser sur les problèmes de type Collatz se divisent empiriquement en deux catégories
- Les questions relativement triviales à prouver
- Les questions pour lesquelles aucun mathématicien ne connaît de méthode de preuve
- Dans Bigfoot, le fait que (b) répète le motif impair·impair·pair·pair, ou le fait qu’après application de la règle de Collatz classique (3n+1), on obtienne toujours un nombre pair divisé par 2 à l’étape suivante, relèvent de la première catégorie
- Presque toutes les autres questions sur le comportement des systèmes de Collatz peuvent être considérées comme relevant de la seconde catégorie
Une expression alternative en 81 cas
- Une expression alternative ajoutée le 18 octobre 2023 réduit les inconvénients de la description précédente avec (A(a,b,c))
- La description précédente présente trois inconvénients
- Les paramètres (b) et (c) sont entremêlés
- Le modulo 6 en entrée et le modulo 8 en sortie ont un facteur commun 2
- (b) suit un motif répétitif impair·impair·pair·pair
- Matthew House a fait remarquer que l’on peut éviter ces problèmes en définissant une nouvelle configuration comme suit
[ B(a,b)=A(a,2b+1,2) ]
- En posant (b=81k+r) et en regroupant quatre transitions d’origine en une seule, le comportement de Bigfoot de type Collatz peut être exprimé par des règles à 81 cas
- Cette expression résout les trois particularités de l’expression (A) précédente et ressemble davantage au problème de Collatz classique
- Toutefois, comme il faut traiter les 81 cas, elle est quelque peu lourde à manier
- Certaines règles dépendent de la condition (a \ge 2)
1 commentaires
Avis de Hacker News
Plutôt que de dire que BB(3, 3) est difficile en soi, il semble plus juste de dire qu’il encode un problème de type Collatz, et que ce genre de problèmes est généralement considéré comme très difficile.
Reste à savoir si cette instance précise est forcément difficile. Son comportement semble assez déséquilibré, et contrairement au problème de Collatz classique, il ne faut pas examiner les trajectoires de tous les entiers, mais seulement une seule trajectoire.
Je suis aussi plutôt d’accord sur la distinction entre trajectoire unique et trajectoires multiples. Cela dit, si l’on suppose que cette machine de Turing se trouve dans un monde où elle ne s’arrête pas, prouver la trajectoire unique de ce système peut être vu comme « plus difficile » que prouver une trajectoire unique dans la conjecture de Collatz classique. Si la conjecture de Collatz est vraie, la preuve de n’importe quelle trajectoire unique se ramène finalement à un calcul fini ; alors que, pour la trajectoire unique de l’article, il faut montrer qu’elle ne s’arrête jamais, ce qui demande des mathématiques plus élaborées.
Je ne veux pas exagérer. Cela ne signifie pas que résoudre BB(3, 3) exige nécessairement de prouver la conjecture de Collatz ou un problème ouvert déjà bien étudié en mathématiques. Mais j’y vois tout de même un résultat « de second choix » intéressant : un problème difficile qui ressemble à un problème bien étudié. On verra à quel point ce problème analogue à Collatz est difficile en regardant qui parvient à le résoudre.
J’aimerais clarifier ma compréhension ici. Il existe une machine de Turing à 748 états [0], et je comprends que cette machine s’arrête uniquement si ZFC est contradictoire.
Cette machine est un objet « physique » que l’on peut implémenter et exécuter sur ordinateur. La puissance de calcul actuelle est insuffisante, mais en principe, rien n’empêche d’exécuter cette machine pendant BB(748) étapes. Si elle s’arrête, alors, d’après le théorème 1, on a prouvé que ZFC est contradictoire ; si elle ne s’arrête pas, on semble avoir prouvé que ZFC est cohérente.
C’est le cœur de ma confusion. Cela ressemble non pas à un résultat abstrait, mais à un calcul que l’on pourrait réellement effectuer pour obtenir une valeur.
Bien sûr, d’après le deuxième théorème d’incomplétude de Gödel, ZFC ne peut pas prouver en son sein sa propre cohérence. Or si la machine de Turing ci-dessus s’arrête, cela semblerait prouver que ZFC est cohérente, ce qui paraît contradictoire.
Où est l’erreur ? Mon hypothèse actuelle est que la preuve du théorème 1 utilise une métathéorie plus forte que ZFC pour montrer que la machine de Turing à 748 états s’arrête uniquement si ZFC est contradictoire. Dans ce cas, il n’y a pas de contradiction. Même si l’on pouvait la faire tourner pendant BB(748) étapes, cela montrerait seulement que ZFC+ prouve la cohérence de ZFC, ce qui est déjà connu. Par exemple, ZFC + « il existe un cardinal inaccessible » peut jouer ce rôle.
Je n’ai pas lu l’article en détail, donc je ne sais pas si c’est réellement le cas. Quelqu’un qui a réfléchi à ce problème en profondeur pourrait-il apporter un éclairage ?
[0] https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-unde...
Si le dieu du castor affairé nous donnait cette valeur, on pourrait théoriquement faire tourner la machine de Turing pendant autant d’étapes et, comme tu le dis, prouver si ZFC est cohérente ou non. Mais pour qu’un humain calcule BB(748), il faudrait en pratique déterminer si cette machine de Turing précise à 748 états finit par s’arrêter, ainsi que si toutes les autres machines de Turing à 748 états s’arrêtent.
Si l’on utilisait toute la matière et toute l’énergie de l’univers pour construire un ordinateur, et que cet ordinateur n’exécutait que cette tâche avec l’efficacité maximale physiquement possible, il ne terminerait pas le calcul.
C’est là qu’apparaît une séparation entre les mathématiques et la physique, la réalité. On peut parler de tels objets et raisonner à leur sujet, mais ils n’ont plus vraiment de signification physique.
Mais prouver qu’elle ne s’arrête pas est beaucoup plus difficile. Même l’exécuter pendant TREE(3) étapes ne prouve pas qu’elle ne s’arrêtera pas à l’étape TREE(3)+1.
Donc, malheureusement, on ne peut pas dire « il suffit de la lancer ».
J’ai apprécié le style de l’auteur. Il aidait à comprendre le sujet sans paraître verbeux, et trouver ce point d’équilibre n’est pas facile.
Ressources connexes : https://nickdrozd.github.io/2020/08/13/beeping-busy-beavers.... et https://googology.fandom.com/wiki/Googology_Wiki
Est-ce que c’est cela que veut dire « BB est non calculable » ? Je me demande si, à mesure que BB grandit, elle finit par contenir toutes les mathématiques, et si cela signifie qu’il faudrait finalement tout démontrer.
Le reste des mathématiques est en quelque sorte introduit clandestinement dans BB via le problème de l’arrêt. On peut écrire un programme qui s’arrête seulement si une conjecture mathématique arbitraire est vraie ou fausse ; chercher à résoudre le problème de l’arrêt ou BB exige donc de connaître toutes les mathématiques[0]. C’est possible parce que la complétude de Turing marque la frontière de la calculabilité. Ce qui peut contenir un ordinateur est lui-même un ordinateur.
[0] En réalité, ce n’est pas cela en soi qui rend l’arrêt indécidable. L’indécidabilité vient du fait qu’un programme « s’entraîne lui-même dans le problème de l’arrêt », par exemple un hypothétique décideur de l’arrêt qui s’arrêterait uniquement lorsqu’il affirme que lui-même ne s’arrête pas.
Il existe des problèmes mathématiques dont nous « savons » que nous ne pouvons ni les démontrer ni les réfuter. C’est ce qu’affirme le premier théorème d’incomplétude de Gödel, sauf dans le cas où toute proposition pourrait être démontrée à la fois vraie et fausse. Si l’on pouvait démontrer toute proposition comme vraie et comme fausse, ce système de preuve serait inutile, et « démontrer » ne voudrait plus rien dire ; il faudrait donc choisir un autre système de preuve où cela n’arrive pas. On suppose donc généralement le premier cas : il existe des problèmes qu’on ne peut ni démontrer ni réfuter. Ajoutons que le deuxième théorème d’incomplétude de Gödel dit que nous ne pourrons jamais démontrer que nous sommes bien dans ce premier cas.
Et dire que BB est non calculable signifie que, lorsque BB devient assez grand, on finit par pouvoir encoder un programme qui ne s’arrête que si un problème ni démontrable ni réfutable est vrai. On ne peut donc pas démontrer si ce programme s’arrête ou non.
Strictement parlant, démontrer ou réfuter quelque chose qui ne peut être ni démontré ni réfuté revient à démontrer une fausseté, ce qui peut ensuite servir à « démontrer » n’importe quelle proposition ; en ce sens, dire que cela « englobe toutes les mathématiques » est en partie juste. Mais c’est une condition critique, et elle se déclenche bien avant l’apparition d’une machine de Turing assez grande pour encoder « tous » les problèmes mathématiques. En fait, il n’existe aucun nombre fini d’états suffisant pour encoder tous les problèmes mathématiques, puisqu’on peut toujours former des chaînes arithmétiques plus longues.
Ensuite, le fait qu’il existe des BB que nous ne pouvons pas résoudre n’a rien d’étonnant ; ce qui devient intéressant, c’est d’étudier quelles BB peuvent être résolues et lesquelles ne le peuvent pas.
Je ne vois pas pourquoi le passage « Ainsi, résoudre le problème BB(3, 3) est au moins aussi difficile que résoudre ce problème de type Collatz » serait surprenant. En fait, cela me semble presque évident à démontrer. Tous les problèmes BB(x, y) ne se réduisent-ils pas à des problèmes de type Collatz ?
BB(x, y) se transforme facilement en problème de l’arrêt. On trouve, parmi toutes les machines à x états et y symboles, celles qui s’arrêtent, et on met de côté celles qui ne s’arrêtent pas. Ensuite, on exécute toutes les machines qui s’arrêtent une étape à la fois, en parallèle, jusqu’à ce qu’elles se soient toutes arrêtées ; le nombre d’étapes exécutées est alors la valeur de BB(x, y).
Il me semble que Conway a proposé une manière de réduire le problème de l’arrêt à des problèmes de type Collatz. Dans ce cas, avec une réduction en deux étapes — de BB vers le problème de l’arrêt, puis vers le problème de Collatz — il semble possible de réduire BB(x, y), pour n’importe quels x et y, à un problème de type Collatz.
Ce qu’il faut, c’est une réduction de Collatz vers le problème de l’arrêt, puis vers B(x,y). La réduction de Collatz vers le problème de l’arrêt est évidente, mais celle du problème de l’arrêt vers B(x,y) l’est moins. Il faudrait définir précisément quel sous-ensemble du problème de l’arrêt peut être réduit depuis Collatz tout en n’étant pas plus difficile que B(3,3).
Le problème de l’arrêt semble souvent « bloquer » la théorie algorithmique de l’information fondée sur des programmes calculables, ainsi que de nombreuses approches de l’induction. Je me demande toutefois s’il existe des travaux sur l’impact matériel du problème de l’arrêt sur notre capacité d’induction dans le monde réel.
Par exemple, supposons qu’un oracle nous dise si une machine de Turing universelle monotone arbitraire a atteint, pendant son exécution, un point où elle n’écrira plus rien sur le ruban de sortie. Les résultats d’induction obtenus avec cet oracle seraient-ils très différents d’une approche consistant à explorer exhaustivement l’espace des programmes, puis à « passer » simplement au programme suivant si un programme ne produit aucune sortie pendant un nombre suffisamment grand n d’étapes ?
Je parle d’induction sur des données « ordinaires » compressibles, pas de cas limites fabriqués exprès comme BB(3,3) ni d’exemples adversariaux.
En tant que chercheur en sécurité, j’écris moi-même des fuzzers. Un fuzzer est un outil qui trouve automatiquement des entrées pertinentes du point de vue de la sécurité pour un programme testé. Il génère et modifie des entrées de manière algorithmique, les fournit au programme, puis observe ce qui se passe, des dizaines, centaines ou milliers de fois par seconde.
Si une entrée fait planter le programme, on peut considérer qu’elle l’a « fait s’arrêter ». Pour créer un fuzzer capable de trouver tous les bugs de n’importe quel programme en un temps réaliste, il faudrait probablement résoudre le problème de l’arrêt. En pratique, certaines personnes trouvent encore des bugs dans des décodeurs d’images après des milliards de tests ; nos fuzzers ne sont donc clairement pas parfaits.
En même temps, dans le monde réel, j’ai vu des fuzzers, quand on leur laisse assez de temps, pénétrer plus profondément que prévu dans des programmes complexes. La validation des entrées effectuée par la cible, ainsi que la mémoire et le stockage limités des PC modernes, placent en quelque sorte le fuzzer sur des rails. La cryptographie fait toutefois exception : pour un fuzzer, c’est comme un bourbier computationnel. Les programmes bien défendus et bien spécifiés jouent le rôle de garde-fous, évitant au fuzzer d’avoir à résoudre le problème de l’arrêt.
Donc, concernant la détection de bugs de sécurité dans les programmes, je vois les choses ainsi : hors cryptographie, les fuzzers sont efficaces pour cibler des programmes qui valident strictement leurs entrées. À l’inverse, pour des programmes qui ne valident pas strictement leurs entrées, on n’a pas vraiment besoin d’un fuzzer, et dans ces cas-là il ne fonctionne pas forcément très bien.
A-t-on une intuition de pourquoi BBB, c’est-à-dire le castor affairé qui émet un bip, peut s’exécuter beaucoup plus longtemps avant le quasi-arrêt ?
Une chose visible, c’est qu’il n’a pratiquement pas besoin d’utiliser l’état d’arrêt. En ce sens, un BBB à 3 états pourrait ressembler à un BB à 4 états. Je me demande s’il y a autre chose
On peut donc faire en sorte qu’un programme ou une machine de Turing de taille X simule l’exécution de tous les programmes de taille Y, avec Y >> X. Si on lui fait émettre un bip chaque fois que l’un de ces programmes s’arrête, le dernier bip se produit lorsqu’il simule l’arrêt de BB(Y) après plus de BB(Y) étapes. Ainsi BBB(X) > BB(Y) >> BB(X)
Si mes souvenirs sont bons, essentiellement à cause de la même construction, connaître BB(N) permet de calculer très lentement le problème de l’arrêt pour les programmes de taille au plus N, tandis que connaître BBB(N) permet de calculer encore bien plus lentement le problème de l’arrêt pour les machines de Turing munies d’un oracle de l’arrêt de taille au plus N
C’est beaucoup trop nerd pour moi
Je me demande quelles connaissances préalables il faut pour comprendre ça. Un niveau de base en calcul différentiel et intégral suffit-il ? Quels sujets ou cours précis constitueraient une bonne base ?
[1] https://www.scottaaronson.com/writings/bignumbers.html
Suivre un manuel d’introduction à l’informatique théorique aidera à en comprendre l’essentiel. Les étudiants en informatique l’étudient généralement en première ou deuxième année, et ce n’est pas facile. Dans mon école, c’était l’un des examens les plus redoutés
Le manuel d’introduction de Hopcroft & Ullman est bon. Cela dit, il y a tellement de notions connexes que c’est plutôt un point de départ
Beaucoup de cursus de licence en informatique doivent proposer des cours avec des ressources publiques
Comment faut-il lire
1RB2RA1LC_2LC1RB2RB_---2LA1LA?https://bbchallenge.org/1RB2RA1LC_2LC1RB2RB_---2LA1LA
Par exemple, si l’on est dans l’état B et que la valeur de la bande à la position actuelle de la tête est 0, on écrit 2, on déplace la tête d’une case vers la gauche, puis on passe à l’état C
Les 3 caractères indiquent le symbole à écrire, le nouvel état et la direction du déplacement. L’état
---correspond à l’arrêt(état, valeur de bande)est associée à un triplet(nouvelle valeur de bande, direction de déplacement de la tête de lecture, nouvel état)[0] https://bbchallenge.org/1RB2RA1LC_2LC1RB2RB_---2LA1LA