Une machine de Turing à 10 états, appelée n1, a été identifiée : elle dépasse le champion actuel BB(10). La borne publiée du champion est f_ω(f_ω(25)), au niveau ω de la hiérarchie à croissance rapide. n1 fait passer le record BB(10) au niveau ω+1. La machine est construite à partir d'une machine de base à 8 états qui coïncide avec le record BB(8) sur les états A à E et exécute le même calcul de liste de chiffres que le record, à savoir le programme du champion BB(7) comportant 36 chiffres.
Les chercheurs ont étendu la machine de base en envoyant sa transition d'arrêt vers un nouvel état I, et en ajoutant les états I et J. La machine s'arrête à partir d'un ruban vierge. Son score exact est démontré dans Coq, un assistant de preuve vérifié par machine, sans aucun axiome. Ce score se situe entre deux valeurs de f_(ω+1), ce qui le place à un niveau plus élevé de la hiérarchie que le champion précédent.
Les preuves établissent que le nombre de 1 laissés sur le ruban dépasse le nombre de Graham, et qu'il est supérieur à F appliquée N = (6T − 19)/7 ≈ 0,86·T fois à 33, où T = 2↑^37 3 est la valeur calculée par le record BB(8). Le score standard est le nombre de uns plus un, car la transition d'arrêt écrit un 1.
L'analyse suit la notation de Ligocki pour le champion BB(7), dans laquelle le contenu du ruban est codé sous forme de blocs de chiffres alternés et de zéros. Chaque étape d'effacement sur un jeton modifie la valeur de l'accumulateur d'une tour d'exponentielles dont la hauteur dépend de la profondeur du jeton. Le résultat est une borne inférieure vérifiée par machine qui éclipse les records précédents.
La machine a été décrite le 8 octobre 2026 et est documentée dans un dépôt public de jeff87654. Ce résultat est important pour le problème du castor affairé, qui cherche le nombre maximal de pas ou de uns qu'une machine arrêtée d'une taille donnée peut produire.
Source: Hacker News · Résumé par HeadlinesBriefing