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

 (sligocki.com)
1 points par GN⁺ 2024-05-25 | 1 commentaires | Partager sur WhatsApp

BB(3, 4) > Ack(14)

  • 22 mai 2024
    • Pavel a découvert une machine de Turing (Turing Machine, TM) à 3 états et 4 symboles
    • Cette machine calcule une fonction de niveau « Ackermann » et s'arrête avec exactement (2↑155)+14 symboles non nuls
    • La notation en flèches montantes de Knuth devenant quelque peu peu pratique, on peut l'approximer ainsi : BB(3,4)>Ack(14)
    • Ici, Ack(14) est défini comme le 14e nombre d'Ackermann : Ack(n)=n↑nn
    • Il s'agit de la première TM capable de simuler une fonction de niveau Ackermann découverte « dans la nature »

Machine

  • Table de transition d'état

    | 0   | 1   | 2   | 3   |
| --- | --- | --- | --- |
| A   | 1RB | 3LB | 1RZ | 2RA |
| B   | 2LC | 3RB | 1LC | 2RA |
| C   | 3RB | 1LB | 3LC | 2RC |

  • Configuration finale

    • 0∞32g153(0)+12161 Z> 0∞
    • Il reste exactement σ=2g153(0)+18=(2↑155)+14 symboles non nuls sur la bande

Attribution

  • Découvreur
    • Cette TM a été découverte par Pavel Kropitz(@uni) et partagée sur Discord le 25 avril 2024
    • Son code ne permettait pas de spécifier une borne lisible par un humain pour le score de la TM, et était simplement indiqué comme Halt(SuperPowers(13))
    • Il a commencé à vérifier ce résultat à l'aide d'un nouveau « validateur de preuve inductive »
    • Le 20 mai 2024, il a extrait une définition exacte de gkn(m) et obtenu la borne σ>2↑153
    • Matthew House(@LegionMammal978) a trouvé le 22 mai 2024 une forme fermée simple de gkn(0)=2↑k(n+2)2−2

Analyse

  • Définition de B(k,n,m)

    B(k,n,m)=0∞32m+12k A> 1n

  • Preuve

    0∞A>0∞→241B(16,3,0)20∞
B(k,n,m)→B(k,0,gk−1n(m)) if k≥1
B(k,0,m)2→10∞32m+12k1Z>

  • Définition de gk(m)

    g0(m)=m+1
gk+1(m)=gk2m+2(0)

Preuve par double induction

  • Règle principale

    B(k,n,m)→B(k,0,gk−1n(m))

  • Lemme 1

    For all k≥1: 32k<B→2k+12k<B1

  • Corollaire 2

    For all k≥1,m≥0: 3m2k<B→(2k+1)m2k<B1m

  • Théorème 3

    For all k≥1,n≥0,m≥0: B(k,n,m)→B(k,0,gk−1n(m))

Valeur exacte

  • Théorème

    For all k≥0,m≥0: 2gk+1(m)+4=2↑k(2m+4)

  • Corollaire

    For all k≥0,n≥0: 2gkn(0)+4=2↑k(n+2)

  • Conclusion

    σ=2g153(0)+18=(2↑155)+14

Permutations

  • Départ depuis l'état B

    σB=2g63(0)+9=(2↑65)+5

  • Départ depuis l'état C

    σC=2g03(0)+3=(2↑05)−1=9 (arrêt en 72 étapes)

  • TNF transformée

    | 0   | 1   | 2   | 3   |
| --- | --- | --- | --- |
| A   | 1RB | 3RB | 1LC | 2LA |
| B   | 2LA | 2RB | 1LB | 3RA |
| C   | 3LA | 1RZ | 1LC | 2RA |

Pas Collatz

  • Points intéressants
    • Cette TM est étonnamment simple
    • Elle n'a pas de règle de type Collatz
    • Cela n'exclut pas la possibilité qu'il existe une TM de niveau Ackermann de type Collatz

Inductive Proof Validator

  • Objectif du projet
    • Développement d'un validateur de « preuve inductive »
    • Développement d'un format de certificat standardisé permettant de vérifier diverses preuves inductives
    • Le projet en est encore à ses débuts, mais a déjà réussi à prouver le comportement de plusieurs TM

Avis de GN⁺

  • Points intéressants

    • Cet article aide grandement à comprendre la complexité des machines de Turing et de la fonction d'Ackermann
    • Il est séduisant de voir que des règles simples peuvent effectuer des calculs complexes

  • Regard critique

    • Comprendre la complexité de cette machine nécessite des connaissances en mathématiques
    • L'accent est davantage mis sur l'intérêt théorique que sur les applications pratiques

  • Technologies liées

    • Le validateur de preuve inductive peut contribuer de manière importante au développement de systèmes automatisés de preuve mathématique
    • Il pourrait aussi s'appliquer à d'autres problèmes de calcul complexes

  • Éléments à prendre en compte

    • Lors de l'adoption de cette technologie, il faut prendre en compte la précision et l'efficacité du processus de vérification
    • Comprendre et appliquer des concepts mathématiques complexes demande du temps

À lire aussi

1 commentaires

 
GN⁺ 2024-05-25
Avis Hacker News

Résumé des commentaires Hacker News

  • Programme de machine de Turing simple
    Contrairement à l’idée qu’un programme de machine de Turing serait un code spaghetti complexe, ce nouveau programme est relativement simple. Il comporte trois états (A, B, C), et l’état B transmet le contrôle à A et C, tandis que A et C ne se connaissent pas mutuellement et ne renvoient le contrôle qu’à B. Cela forme une structure modulaire ; dans un véritable code spaghetti, chaque état pourrait transmettre le contrôle à tous les autres.

  • Caractéristiques intéressantes
    Ce programme n’écrit pas de case vide, et toutes les instructions changent soit l’état, soit la couleur. Le nouveau détenteur du record BB(3,4) contient environ 64 bits d’information. BBλ(49), avec 49 bits, dépasse très largement le nombre de Graham.

  • Exemple d’implémentation
    Après avoir implémenté directement le programme, il apparaît que l’état B transforme 0 en 2 et 1 en 1, puis passe à C, tandis que l’état C transforme 3 en 2 puis passe à A. Cela produit des suites de 3 dont la longueur croît exponentiellement.

  • Ressemblance avec le code golf
    Tout cela ressemble à du code golf extrême. Un projet personnel appelé BitGrid ne dispose que d’un état de 4 bits par cellule, et une grille 4x4 peut compter jusqu’à 2^64 au maximum. Sur de petites grilles, la connexion des bords a un effet majeur sur le résultat.

  • Demande de ressources pour interpréter la machine de Turing
    Demande de ressources expliquant comment lire le tableau. Cela semble être une description d’une machine de Turing.

  • Limites des machines de Turing
    Le nombre de machines de Turing qu’on peut décrire avec un nombre limité de symboles est fini. Il est étonnant que certaines puissent exécuter un nombre immense d’étapes avant de s’arrêter.

  • Demande d’explication sur ce qui est spécial
    Demande d’explication sur ce qui rend cet ensemble d’instructions particulier si impressionnant. Interrogation sur ce qu’est une fonction du niveau de la fonction d’Ackermann et sur ce qu’elle calcule réellement.

  • Intérêt pour les vérités mathématiques
    Un résultat qui semble inutile est jugé plus intéressant que les avancées très utiles des LLM. Cela vient d’une attirance naturelle pour des vérités mathématiques simples.

  • Comparaison entre BB(5) et BB(3,4)
    Question sur le fait de savoir si BB(5) est plus grand que BB(3,4). Le site bbchallenge.org indique que BB(5) vaut environ 47 millions, alors que BB(3,4) serait bien plus grand.

  • Contexte apporté par l’auteur
    Le fait que l’auteur fournisse un peu de contexte est apprécié.