Castor de cerveau occupé

13

Écrivez un programme de brainfuck de pas plus de 256 caractères qui prend autant d'étapes que possible, mais ne boucle pas indéfiniment. Le programme ne peut prendre aucune entrée.

Plus précisement:

  • Supposons un nombre infini de cellules à droite.
  • Un <quand à la cellule la plus à gauche ne fait rien.
  • Un -lorsque la valeur de la cellule est nulle définit la cellule sur 255.
  • Les instructions +-<>.comptent toutes comme une étape lorsqu'elles sont exécutées.
  • Lorsqu'un [ou ]est rencontré, cela compte comme une étape. Toutefois, si la condition est vraie et saute flux de contrôle, le correspondant ]ou [ne pas compter à nouveau comme une étape.
  • La solution qui prend le plus de pas gagne.
  • S'il existe une sorte de modèle dans votre solution, donner une fonction pour le nombre de pas qu'un programme similaire de longueur nprendrait est apprécié mais pas obligatoire.
  • Pour compter les instructions, vous pouvez utiliser cet interpréteur modifié :

Exemple:

++[-]

Les instructions rencontrées le sont ++[-]-]et le programme s'est exécuté en 7 étapes.

Anton Golov
la source
6
Je serais surpris si le gagnant terminait sans déborder le compte de l'interprète. Gardez à l'esprit que le castor occupé à 6 états TM prend au moins 10 ** 36534 pas.
Peter Taylor
Je suis d'accord. Il semble très probable que vous puissiez écrire un programme BF <50 caractères qui pourrait fonctionner pendant des années. Je vais commencer.
captncraig
Signé. La page de recherche Busy Beaver sur drb.insel.de/~heiner/BB est très intéressante, en particulier le fait que les programmes d'enregistrement durent extrêmement longtemps et qu'ils ont toujours des résultats exacts (voir drb.insel.de/~heiner/BB/bb -xlist.txt ) - les simulations se souviennent des états, construisent des "macros" pour enregistrer les étapes de simulation, etc.
schnaader
4
@AntonGolov: malheureusement, dans cet univers, les RAM et les HD ne se convertissent pas en périphériques de stockage infinis lorsque vous essayez de stocker des bignums d'une taille supérieure à 256 ^ en octets ...
cessé de tourner dans le sens inverse des aiguilles d'une montre du
1
@boothby Il est parfaitement possible de faire des calculs exacts impliquant des transcendantaux sur les ordinateurs actuels. Les composants des valeurs doivent simplement être stockés dans une représentation plus abstraite que la normale floatou les doubleprimitives utilisées pour l'informatique quotidienne générale. (À ce stade, l'ordinateur manipule principalement des chaînes qui représentent l'équation)
AJMansfield

Réponses:

15

Voici un programme de 41 caractères qui s'arrête finalement, laissant plus de 10 ↑ (10 ↑ 28) cellules contiguës définies égales à 1 (le nombre d'instructions exécutées est donc bien supérieur à cela):

>+>+>+>+[->[>]+[->[>]+[->[>]+[<]+<]+<]+<]

Si je ne me trompe pas, c'est une traduction correcte du programme suivant dans le langage de variante BF qui utilise un seul bit pour chaque cellule de mémoire (c'est-à-dire, le contenu de la cellule 0..1 au lieu de 0..255, donc '+' agit simplement pour inverser la valeur du bit):

>+>+>+>+[+>[>]+[+>[>]+[+>[>]+[<]+<]+<]+<]

La valeur exacte (le nombre de bits adjacents 1) produite par ce dernier programme est

3 * (2 ↑ 118842243771396506390315925503 - 1) + 1.


Le programme ci-dessus initialise et calcule une fonction qui grandit comme 2 ↑↑ x (en notation de flèche vers le haut de Knuth ). Une conversion similaire d'un programme variant-BF qui initialise et calcule une fonction qui grandit comme 2 ↑ 23 x fournit le programme de 256 caractères suivant:

>+>+>+>+>+>+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+

qui s'arrête finalement, laissant plus de 2 ↑ 23 6 cellules adjacentes définies égales à 1 (donc le nombre de pas est énormément plus que cela).

NB-1 : 2 ↑ 23 6 est un nombre "inconcevablement grand"; par exemple, même 2 ↑ 4 6 = 2 ↑↑↑↑ 6 dépasse déjà le premier terme (3 ↑↑↑↑ 3) dans la séquence utilisée pour calculer le nombre de Graham .

NB-2 : Je pense qu'il est probable que 256 caractères suffisent pour qu'un programme BF initialise et calcule une fonction avec une sortie beaucoup plus grande que le nombre de Graham - si je trouve du temps, j'essaierai peut-être d'en écrire un.

NB-3 : Si quelqu'un s'intéresse à l'origine des programmes ci-dessus, voici quelques ressources de programmation pour "Brainf * ck F" , avec divers programmes écrits en Python. ("Brainf * ck F", ou simplement "F", est ce que j'ai appelé une variante Turing-complète de l' esolangage Smallf * ck .) Je viens de télécharger ces fichiers, qui sont hors ligne depuis plusieurs années, et pour l'instant le la page Web liée n'est qu'un "classeur" - voir le fichier Busy_Beavers.txt pour une discussion détaillée concernant les programmes ci-dessus.

res
la source
C'est un gagnant clair pour le moment (sauf si je sous-estime juste les autres). D'autres suggestions sont les bienvenues, mais je les marquerai comme acceptées pour l'instant. Si quelqu'un n'est pas d'accord, veuillez commenter.
Anton Golov
Lorsque vous atteignez ce niveau, il devient irréaliste de supposer que vous avez un interprète avec une mémoire infinie. Je commence à penser que ce serait un meilleur défi avec la mémoire d'emballage finie, afin que nous puissions réellement exécuter les réponses.
captncraig
9

Voici un joli 39 caractères:

-[>-[>-[-[>+<-]<[>+<-]<[>+<-]>>>]<-]<-]

Il fait essentiellement un «traîneau» de 3 espaces qu'il se déplace vers la droite et diminue d'une unité. Terminé en 31 919 535 558 instructions, la boucle la plus interne s'exécutant 256 ^ 3 fois. J'ai encore beaucoup de place pour étendre cela assez loin à un taux de 14 caractères à un autre ordre de grandeur pour la durée d'exécution.

Fonctionne sur n'importe quel interpréteur avec une mémoire illimitée ou avec une mémoire d'habillage.

Je laisse un exercice au lecteur pour déterminer quand la version améliorée par 2 boucles se terminera:

-[>-[>-[>-[>-[-[>+<-]<[>+<-]<[>+<-]<[>+<-]<[>+<-]>>>>>]<-]<-]<-]<-]

Il a maintenant fonctionné du jour au lendemain et se compose de plus de 3 000 000 000 de pas. N'a pas encore traversé une seule itération de la boucle externe. A à peine franchi 15% de la seconde boucle.

captncraig
la source
2

Ce programme fonctionne dans un nombre infini de cellules. Deux valeurs sont initialisées au début avec des valeurs ascii 255. La première valeur à la première rotation de la boucle principale est divisée en 255 cellules et elles sont initialisées avec 255 chacune, à la deuxième rotation de la boucle principale, chaque valeur en 255 cellules se divise à nouveau jusqu'à 255 * 255 cellules, de la même manière pour 255 rotation de la boucle principale, le total des cellules initialisées sera 255 ^ 255. La deuxième valeur détermine combien de fois la boucle principale doit être répétée.

>->>-[<<[<]>[[[>]>>>[>]-[<]<<<[<]>-]>]>[>>[>]>+<<[<]<-]>>[>]>-]
Albert
la source
2

Ce programme est presque le même que mon programme précédent, la différence est que la valeur déterminant la boucle externe reste fixe dans une cellule particulière, de sorte que le nombre de cellules initialisées et le nombre total d'étapes à la fin du programme peuvent être augmentés

->>-<<[>>[>]<[[>>[>]-[<]<-]>>[[<+>-]>]<<[<]<]>>[[<+>-]>]<<[<]<-]

cellules initialisées à la fin du programme 255 ^ 255

-[>-[>->>[-]-<<[>>[>]<[[>>[>]-[<]<-]>>[[<+>-]>]<<[<]<]>>[[<+>-]>]<<[<]<-]<-]<-]

cellules initialisées à la fin du programme 255 ^ 255 ^ 3

Je l'ai encore modifié pour exécuter encore plus de nombre d'étapes.

->>>->>-<<<<<[>>>[>]<[[>>[>]<[[>>[>]-[<]<-]>>[[<+>-]>]<<[<]<]>>[[<+>-]>]<<[<]<-]<[>>>[[<+>-]>]<<[<]]<]>>>>[[<<+>>-]>]<-<<[<]<<-]

il initialise 255 ^ 255 cellules lors de la première rotation de 255 ^ (255 ^ 255 * 255) cellules lors de la deuxième rotation de la boucle principale 255 ^ {255 ^ (255 ^ 255 * 255) * 255} cellules lors de la troisième rotation de la boucle principale dans cette boucle se répète 255 fois

Albert
la source
Ça a l'air super! Désolé de ne pas avoir encore accepté de réponse - je dois prendre le temps de les examiner et de déterminer l'ordre de croissance. Lorsque vous dites "255 ^ 255 * 255", voulez-vous dire "255 ^ (255 * 255)"? (Je m'attendrais à ce que "255 ^ 256" autrement.)
Anton Golov