Résultat : BB(3, 4) > Ack(14)

 (sligocki.com)
1 points par GN⁺ 2024-05-25 | 1 commentaires | Partager sur WhatsApp
  • Un nouveau champion TM Busy Beaver à 3 états et 4 symboles a été découvert ; il est calculé qu’à l’arrêt, il laisse ((2 \uparrow^{15} 5) + 14) symboles non nuls
  • Ce nombre est immense même en notation des flèches de Knuth, ce qui donne une borne inférieure (BB(3,4) > Ack(14)), supérieure au 14e nombre d’Ackermann, défini par (Ack(n)=n \uparrow^n n)
  • Le comportement essentiel de la TM se compresse presque en (B(k,n,m) \to B(k,0,g_{k-1}^n(m))), mais le démontrer nécessite une double induction
  • Grâce à l’expression fermée d’évaluation de Matthew House (g_k^n(0)=\frac{2 \uparrow^k (n+2)}{2}-2), le score final (\sigma=(2 \uparrow^{15}5)+14) peut être écrit exactement
  • Cette TM simule une fonction de niveau Ackermann sans branchement de type Collatz sur des restes, et sert aussi de cas de validation pour l’Inductive Proof Validator en développement

Échelle du nouveau champion Busy Beaver

  • Pavel Kropitz a découvert un nouveau champion Busy Beaver à 3 états et 4 symboles
  • Cette TM peut calculer une fonction « de niveau Ackermann » et, lorsqu’elle s’arrête, laisse le nombre suivant de symboles non nuls sur la bande
    • ((2 \uparrow^{15} 5) + 14)
  • La valeur est énorme même en notation des flèches de Knuth ; la borne inférieure se résume ainsi
    • (BB(3,4) > Ack(14))
  • Ici, (Ack(14)) est le 14e nombre d’Ackermann, défini par (Ack(n)=n \uparrow^n n)
  • Parmi les machines de Turing découvertes lors de recherches effectives connues, c’est le premier exemple capable de simuler une fonction de niveau Ackermann

Définition de la TM et configuration finale

  • La chaîne de transitions de la TM est la suivante
    • 1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC
  • La table de transitions est définie pour les états A, B, C et les symboles 0, 1, 2, 3
    • A : 1RB, 3LB, 1RZ, 2RA
    • B : 2LC, 3RB, 1LC, 2RA
    • C : 3RB, 1LB, 3LC, 2RC
  • La configuration finale est la suivante
    • (0^\infty ;; 3^{2 g_{15}^{3}(0) + 1} ;; 2^{16} ;; 1 ;; \text{ Z> } ;; 0^\infty)
  • Dans cette configuration, le score (\sigma) se calcule exactement
    • (\sigma = 2 g_{15}^{3}(0) + 18 = (2 \uparrow^{15} 5) + 14)

Découverte et processus de vérification

  • Pavel Kropitz a partagé cette TM le 25 avril 2024 sur Discord
  • À l’époque, le code ne pouvait pas indiquer de borne inférieure du score lisible par un humain et affichait le résultat sous la forme Halt(SuperPowers(13))
    • Cela signifie que la preuve nécessite 13 niveaux de règles inductives
  • La vérification a ensuite commencé avec le nouvel Inductive Proof Validator
  • Le 20 mai 2024, la vérification a été achevée, ce qui a permis d’extraire la définition exacte de (g_k^n(m)) et d’obtenir ainsi la borne inférieure (\sigma > 2 \uparrow^{15} 3)
  • Matthew House a découvert le 22 mai 2024 l’expression fermée simple suivante
    • (g_k^n(0) = \frac{ 2 \uparrow^k (n+2) }{2} - 2)
  • Cette expression d’évaluation a rendu possible l’expression de la valeur exacte de (\sigma)

Analyse du comportement et preuve par double induction

  • On définit la configuration suivante
    • (B(k, n, m) = 0^\infty ;; 3^{2m+1} ;; 2^k ;; \text{ A> } ;; 1^n)
  • Après 241 étapes, la configuration initiale atteint l’état suivant
    • (0^\infty ;; \text{A>} ;; 0^\infty \xrightarrow{241} B(16,3,0);;2;;0^\infty)
  • La règle essentielle est la suivante
    • (B(k,n,m) \to B(k,0,g_{k-1}^n(m))), avec (k \ge 1)
  • (g_k) est défini par la récurrence suivante
    • (g_0(m)=m+1)
    • (g_{k+1}(m)=g_k^{2m+2}(0))
  • Le comportement global est assez simple pour se compresser presque en une seule règle, mais cette règle elle-même doit être démontrée par double induction
  • Les lemmes et corollaires traitent la manière dont l’état B transforme les blocs de 3 et de 2^k pour produire des 1
    • (3;;2^k;;\text{<B} \xrightarrow{2k+1} 2^k;;\text{<B};;1)
    • (3^m;;2^k;;\text{<B} \xrightarrow{(2k+1)m} 2^k;;\text{<B};;1^m)
  • Le théorème 3 montre que la règle essentielle vaut pour tous (k \ge 1, n \ge 0, m \ge 0)
    • Le cas de base (k=1) est traité par induction sur (n)
    • L’étape d’induction utilise à la fois l’hypothèse sur (k) et l’hypothèse d’induction sur (n)

Calcul de la valeur exacte

  • (g_k) admet une évaluation fermée relativement simple n’utilisant que les flèches de Knuth et l’arithmétique
  • Pour tous (k \ge 0, m \ge 0), on a
    • (2 g_{k+1}(m) + 4 = 2 \uparrow^k (2m+4))
    • Ici, (a \uparrow^0 b = ab)
  • Ce résultat se démontre par induction sur (k)
    • Dans le cas de base (k=0), on obtient (g_1(m)=2m+2)
    • L’étape d’induction utilise l’application répétée de ((2 \uparrow^k)^n)
  • La forme fermée repose sur la coïncidence selon laquelle (2 \uparrow^k 2 = 4) vaut pour tout (k)
    • Si les paramètres avaient légèrement changé pour prendre une forme ((2 \uparrow^k)^{2m+2}5), il aurait probablement été difficile d’obtenir une expression fermée
  • En corollaire, pour tous (k \ge 0, n \ge 0), on a
    • (2 g_k^n(0) + 4 = 2 \uparrow^k (n+2))
  • Le score final s’en déduit directement ainsi
    • (\sigma = 2 g_{15}^{3}(0) + 18 = (2 \uparrow^{15} 5) + 14)

Résultat des permutations avec changement d’état initial

  • Si l’on remplace l’état initial par B ou C, on obtient des résultats apparentés mais plus petits
    • (0^\infty ;; \text{B>} ;; 0^\infty \xrightarrow{86} B(7,3,0);;2;;0^\infty)
    • (0^\infty ;; \text{C>} ;; 0^\infty \xrightarrow{20} B(1,3,0);;2;;0^\infty)
  • Le score lorsque l’état initial est B est le suivant
    • (\sigma_B = 2 g_6^3(0) + 9 = (2 \uparrow^6 5) + 5)
  • Lorsque l’état initial est C, la machine s’arrête au bout de 72 étapes et le score est le suivant
    • (\sigma_C = 2 g_0^3(0) + 3 = (2 \uparrow^0 5) - 1 = 9)
  • La première permutation qui démarre en B est également une autre TM BB(3,4) de tout premier plan
  • Convertie en TNF, elle donne la chaîne de transitions suivante
    • 1RB3RB1LC2LA_2LA2RB1LB3RA_3LA1RZ1LC2RA

Simplicité sans règle de type Collatz

  • L’un des aspects intéressants de cette TM est qu’elle est plus simple qu’attendu
  • Elle ne comporte pas de règle de type Collatz changeant de comportement selon le reste d’une valeur
  • Il est encore trop tôt pour savoir si la domination des TM de type Collatz est terminée
  • Il est possible qu’il reste des TM de type Collatz de niveau Ackermann, mais qu’elles ne soient pas immédiatement visibles à cause d’un biais de sélection
  • Cette TM a peut-être été découverte comme première TM de niveau Ackermann parce qu’elle était assez simple pour permettre une preuve d’arrêt sans avoir à implémenter d’arithmétique modulaire au-dessus d’une fonction de niveau Ackermann

Inductive Proof Validator

  • Cette TM convenait comme cas de test pour l’Inductive Proof Validator en développement
  • L’objectif du projet est de créer un format de certificat standardisé pour les « preuves inductives »
  • Ici, « preuve inductive » est utilisé comme terme générique couvrant le raisonnement vers l’avant et l’analyse à base de règles en général
  • L’idée est que toute personne disposant d’un « inductive decider » puisse écrire les règles correspondantes dans ce format, afin que le validator puisse vérifier la preuve
  • Le système reste encore très rudimentaire et n’est pas prêt pour un usage réel, mais, moyennant un peu de travail manuel, il a été utilisé pour prouver le comportement de plusieurs TM, dont celle-ci

À lire aussi

1 commentaires

 
GN⁺ 2024-05-25
Avis sur Hacker News

  • On pourrait facilement penser qu’un programme de machine de Turing qui s’exécute très longtemps est profondément complexe ou relève du code spaghetti, mais le nouveau champion ressemble plutôt à un contre-exemple
    Il ne compte que trois états, A, B et C ; B passe le contrôle à A et C, mais A et C ne se « connaissent » pas mutuellement et ne reviennent qu’à B
    Dans du vrai code spaghetti, chaque état aurait pu passer à tous les autres, alors qu’ici il s’agit d’une sorte de construction modulaire
    De plus, il n’écrit jamais de case vide, et chaque instruction change soit l’état, soit la couleur ; il n’y a donc pas non plus de « commande paresseuse » qui ne fait que déplacer la position, comme B1 -> 1LB

    • Même au sein du projet bbchallenge, il y a débat pour savoir si les propriétés des champions actuels à longue exécution sont réellement celles des machines qui s’exécutent le plus longtemps à cette taille, ou si l’on ne voit que les propriétés faciles à trouver par recherche automatique et à prouver, un effet réverbère
      On ne pourra pas le savoir tant que tout l’espace de recherche n’aura pas été exclu, de façon déterministe ou heuristique
      Toutes les tailles au-delà de BB(5, 2) contiennent des machines chaotiques et pseudo-aléatoires dont on s’attend à ce qu’elles s’exécutent indéfiniment, mais qu’il est impossible de prouver sans avancées majeures en théorie des nombres
      Cela dit, on peut penser qu’une machine à longue exécution ne peut pas être complètement chaotique
      Si elle déversait sur la bande des symboles comme des nombres aléatoires, elle finirait vite par atteindre une configuration d’arrêt, une configuration cyclique ou un motif simplifié
      Il reste toutefois possible qu’une machine simule quelque chose de chaotique à un niveau plus élevé, passe un temps absurdement long entre chaque étape de haut niveau, puis s’arrête
    • Une machine de Turing à n états et s symboles ne peut effectuer de transitions que vers au plus n états différents
      Donc, avec s=4 ou s=2, seules de très petites machines de Turing peuvent vraiment ressembler à du code spaghetti

  • Le nouveau détenteur du record BB(3,4) est le suivant
    0 1 2 3
    A 1RB 3LB 1RZ 2RA
    B 2LC 3RB 1LC 2RA
    C 3RB 1LB 3LC 2RC
    La valeur (t', d, s') à la ligne s et à la colonne t désigne la transition lorsque, dans l’état s, le symbole sous la tête de lecture sur la bande est t
    Elle remplace le symbole t par t', se déplace à gauche ou à droite selon la direction d, puis change l’état en s' ; si s' == Z, la machine s’arrête
    Cela représente 3*4*log2(4*2*log2(4+1)), soit environ 64 bits d’information
    À l’inverse, BBλ(49), avec seulement 49 bits, dépasse de très loin le nombre de Graham https://oeis.org/A333479

    • Compter le nombre de machines de Turing distinctes n’a rien de simple
      Le calcul ci-dessus est la méthode la plus large, qui suppose que chaque case peut prendre n’importe quelle combinaison (symbole, direction, état) ; il surestime donc fortement le nombre de bits nécessaires pour décrire une machine de Turing arbitraire
      Dans le cas de BB(3, 4), en utilisant la Tree Normal Form, c’est-à-dire l’algorithme de Brady (https://nickdrozd.github.io/2022/01/14/bradys-algorithm.html), on n’obtient qu’environ 600 milliards de machines de Turing distinctes, soit moins de 40 bits
    • Dans ce programme, le 1R de 1RZ ressemble à une valeur choisie arbitrairement
      Comme la machine s’arrête à ce moment-là, peu importe ce qui reste sur la bande ou l’endroit où la tête se déplace
      En réalité, écrire 1 n’est pas important non plus, mais écrire 0 n’aurait probablement pas été optimal
      À cette position, il y avait déjà un 2, qui est remplacé par 1, mais si l’on compte le nombre de symboles sur la bande, 2 aurait été compté de la même façon
    • Je ne vois pas bien d’où vient le terme log2(4+1)
      Quand je calcule 3*4*log2(4*2*log2(4+1)), j’obtiens environ 51, et du point de vue d’un non-spécialiste j’aurais plutôt pensé à 3*4*log2(4*2*4) = 60
      Je me demande si ce n’est pas plutôt 3*4*log2(4*2*log2(3*3*4-1)) ≈ 64

  • Par curiosité sur son fonctionnement, je l’ai implémentée ici : turingmachine.io/?import-gist=c862f28918f3d889f964797694d28fcc
    En l’exécutant un instant, on voit ce qui se passe
    L’état B remplace 0 par 2 et 1 par 1, puis passe à C ; l’état C remplace 3 par 2, puis passe à A
    Ainsi, pour corriger 2 -> 1, il faut traverser tous les 3, ce qui fait croître de façon répétée et exponentielle les segments consécutifs de 3

    • Il est assez facile de construire une machine de Turing qui croît exponentiellement indéfiniment
      Ce qui est vraiment difficile à comprendre, c’est pourquoi elle finit par s’arrêter après un nombre d’étapes inimaginablement grand

  • Tout cela ressemble à du code golf extrême
    Dans une autre direction, on peut regarder quelque chose appelé BitGrid
    Dans BitGrid, chaque cellule n’a que 4 bits d’état ; une grille de cellules 4x4 ne peut donc en aucun cas compter au-delà de 2^64
    Il serait intéressant de trouver jusqu’où elle peut réellement compter, et dans les petites grilles, la connexion des bords dominera le résultat
    https://esolangs.org/wiki/Bitgrid
    https://github.com/mikewarot/Bitgrid

  • Ce tableau est sans doute une description de machine de Turing ; ce serait bien d’avoir des ressources pour savoir comment l’interpréter

    • Les états A, B, C correspondent aux cibles de goto, et les couleurs 0, 1, 2, 3 sont les données manipulées pendant l’exécution
      À chaque état, on lit la couleur courante puis, selon cette couleur, on exécute l’instruction indiquant « quelle couleur écrire, s’il faut se déplacer à gauche/droite, et vers quel état aller »
      Si on le traduit en C, cela peut s’exprimer tel quel avec switch (SCAN), WRITE, RIGHT/LEFT et goto
      Je me demande s’il y a moyen de réécrire cette logique dans un style plus structuré, ou de l’optimiser autrement
    • Chaque ligne est un état, et chaque colonne est le symbole qui vient d’être lu sur le ruban
      Par exemple, la première ligne et la première colonne signifient : « le symbole 0 a été lu et l’état courant est A »
      La case du tableau indique l’action à effectuer ; 1RB veut dire « remplacer le symbole du ruban par 1, se déplacer d’une case vers la droite, puis passer à l’état B »
      L’état Z correspond à l’état d’arrêt
    • En Python, il suffit de définir des fonctions L() et R() qui déplacent l’indice du ruban vers la gauche/droite, de créer une table qui associe (état, symbole courant) à (symbole à écrire, fonction de déplacement, état suivant), puis de boucler tant que state != 'Z'
    • Une explication simple se trouve sur https://bbchallenge.org/story#turing-machines
      1RZ peut être compris comme une transition d’arrêt, puisqu’il n’y a pas de règle pour l’état Z
      Wikipedia propose aussi un exemple plus détaillé de table d’états de machine de Turing https://en.wikipedia.org/wiki/Turing_machine#Formal_definition, et la trace d’exécution de cette machine de Turing particulière est visible sur https://bbchallenge.org/1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC
    • J’ai créé un petit dépôt qui regroupe les détenteurs actuels des records et montre aussi un exemple d’exécution en Wolfram Language : https://datarepository.wolframcloud.com/resources/The-Busy-Beaver-Competition/
      Il va falloir le mettre à jour, apparemment

  • Voir le résultat majeur d’un domaine fondamental de l’informatique cité via un lien Discord, quand même

    • Je ne vois pas pourquoi ce serait un problème
      L’idée que la seule manière valable de publier des résultats scientifiques serait les soi-disant revues à comité de lecture est un vestige d’il y a 200 ans, quand la communauté scientifique était assez petite pour tenir dans le nombre de Dunbar
      Si ce système perdure, c’est parce qu’une poignée d’universitaires et d’éditeurs puissants en tirent profit, pas parce qu’il aurait de vrais avantages pour le progrès scientifique
      Il est même possible qu’il porte une responsabilité assez importante dans la crise moderne de la reproductibilité
      Je soutiens fermement la méthode scientifique, mais je pense que l’évaluation par les pairs traditionnelle a dépassé sa date de péremption depuis longtemps
      https://en.wikipedia.org/wiki/Dunbar%27s_number
    • Cela dit, c’est un serveur Discord public, et on trouve le lien d’invitation en haut à droite de https://bbchallenge.org
      Je vois plutôt ça comme une indication de source que comme une citation
      Les principaux arguments qui étayent le résultat sont reproduits sous une forme plus rigoureuse dans l’article de blog, donc ils tiennent indépendamment ; les liens Discord ne fournissent qu’un contexte historique pour les personnes intéressées
    • Quand on participe à ce genre de chat, cela ressemble au fait de trouver une idée sur le tableau blanc d’une salle de pause et de la développer ensemble, sauf qu’on peut citer les interactions
      Si cela peut être complété par la littérature au moment opportun, c’est une évolution positive
    • Je comprends la plainte, mais beaucoup des avancées impressionnantes récentes en mathématiques sont venues d’une collaboration et d’itérations rapides
      Par exemple, le projet qui a amélioré la borne supérieure sur les écarts entre nombres premiers de Zhang ; de ce point de vue, d’autres outils de communication ne remplacent peut-être pas facilement Discord
      Il faut aller là où se trouvent réellement les gens
    • Chercher de plus grands nombres de castor affairé relève moins exactement d’un travail fondamental que des mathématiques récréatives
      Si c’était vraiment fondamental, cela aurait fait l’objet d’un article de revue évalué par les pairs, plutôt que d’un billet de blog

  • Les machines de Turing qui peuvent être décrites avec un nombre de symboles pas trop grand, comme 1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC, sont en nombre limité
    Mais le fait que certaines d’entre elles puissent exécuter un nombre aussi absurdement grand d’étapes avant de s’arrêter est vraiment étonnant

    • Il existe 2^60 machines de Turing de ce type, à 3 états et 4 symboles
      Ce qui devrait être encore plus étonnant, c’est un terme lambda de 49 bits dont la sortie, c’est-à-dire la forme normale, dépasse le nombre de Graham

  • Honnêtement, je ne comprends pas tout à 100 %, et ce sont probablement des résultats presque inutiles, mais ils m’attirent davantage que les progrès des LLM, pourtant incroyablement utiles
    C’est sans doute parce que je suis naturellement plus attiré par les vérités mathématiques simples que par les résultats d’ingénierie « complexes »

  • Ne serait-ce pas BB(5) > BB(3,4) ?
    Sur https://bbchallenge.org, il est écrit qu’ils cherchent à prouver ou réfuter la conjecture selon laquelle BB(5) vaut environ 47 millions, alors que BB(3,4) semble beaucoup plus grand

    • Oui, BB(3, 4) >>> BB(5, 2) semble correct
      BB(5) = BB(5, 2), et BB(3, 4) a 12 transitions (3*4) dans sa table, tandis que BB(5, 2) n’en a que 10, donc ce n’est pas si surprenant
      Mais il semble aussi que BB(3, 4) >> BB(6, 2)
      Comme les deux ont le même nombre de transitions, dans ces petites machines de Turing, avoir davantage de symboles semble assez précieux