Math
La machine de Turing et les castors affairés
Un ruban de papier entre deux bobines, une tête métallique avec une lampe d'état et une table de règles. Chaque pas se joue en lire, écrire, déplacer, nouvel état ; le journal en bas garde toute l'exécution, et une règle modifiée conserve l'ancienne en fantôme. Les records sont trouvés en énumérant toutes les machines, pas cités.
Ce qui se passe
Une machine aussi petite est une table et rien d'autre : pour chaque état et chaque symbole, quoi écrire, où aller, quel état suit - ou s'arrêter. Sur le bureau c'est un appareil : un ruban de papier entre deux bobines, une tête sur rails avec une lampe qui montre son état. Chaque pas se joue en quatre phases - la tête lit la case, tamponne le nouveau chiffre, glisse d'une case, la lampe change de couleur - et la feuille en bas tient le journal : chaque pas de l'exécution en carte de chaleur avec un axe du temps. Cliquez un pas pour y tenir la machine. Cliquez un jeton de la table pour changer une règle : l'exécution d'avant reste en fantôme de verre à côté de la nouvelle, avec le pas où les deux histoires se séparent. Le castor affairé demande combien de temps une telle machine peut tourner avant de s'arrêter. Les records ici ne sont pas cités : les 64 machines à un état, les 20736 à deux et 1048576 à trois états en forme normale sont construites et exécutées - trois états donnent au plus 21 pas et au plus 6 uns, par deux machines différentes. Quatre états coûtent 268 millions de machines, donc ce champion est pris comme connu et vérifié en l'exécutant : 107 pas, 13 uns. Une machine qui atteint le plafond de 400 pas ne s'est pas arrêtée, et rien sur cette carte ne peut dire si elle le fera un jour.
Équations du module
Équations une machine est une table : pour chaque (état, symbole) elle dit quoi écrire, où se déplacer (L ou R) et quel état vient ensuite - ou H, l'arrêt le ruban commence rempli de zéros et n'est pas borné ; la fenêtre de la fiche contient 49 cellules, assez pour chaque machine qu'elle exécute S(n) - le plus grand nombre de pas que fait une machine qui s'arrête avec n états ; Σ(n) - le plus grand nombre de uns que laisse l'une d'elles trouvé ici par énumération, non cité : n = 1 donne 64 machines, n = 2 donne 20736, n = 3 donne 16^5 = 1048576 en forme normale (premier coup 1RB) S(1) = 1, Σ(1) = 1 ; S(2) = 6, Σ(2) = 4 ; S(3) = 21, Σ(3) = 6 - et pour n = 3 ce sont deux machines DIFFÉRENTES relever la limite de pas de 25 à 200 n'ajoute aucune machine qui s'arrête : toute machine à 3-états qui s'arrête, s'arrête au pas 21 au plus n = 4 coûterait 16^7 = 268435456 machines, donc son champion est pris comme connu et vérifié en l'exécutant : 107 pas, 13 uns S(n) croît plus vite que toute fonction calculable - c'est pourquoi le tableau ci-dessus s'arrête à quatre et non à dix
