En tant que suivi du programme de terminaison le plus court dont la taille de sortie dépasse le nombre de Graham et Golf un nombre plus grand que TREE (3) , je présente un nouveau défi.
Le nombre de Loader est un très grand nombre, ce qui est un peu difficile à expliquer (car il était lui-même le résultat d'un exercice de golf avec un objectif flexible). Il y a une définition et une explication ici , mais à des fins d'auto-confinement, je vais essayer de l'expliquer plus tard dans ce post également.
L'algorithme utilisé par Ralph Loader produit l'un des plus grands nombres d'algorithmes (calculables) jamais écrits! En effet, le numéro de Loader est le plus grand numéro «calculable» du Googology Wiki. (Par nombre "calculable", ils signifient un nombre défini en termes de calcul.) Cela signifie que si la réponse produit un nombre supérieur au nombre de Loader d'une manière intéressante (c'est-à-dire pas seulement le numéro de Loader + 1), vous pouvez descendre dans Histoire de la googologie! Cela étant dit, les programmes qui produisent quelque chose comme Loader number + 1 sont certainement des réponses valides et des candidats à cette question; ne vous attendez pas à la gloire.
Votre travail consiste à créer un programme de terminaison qui produit un nombre supérieur au nombre de Loader. C'est le code-golf , donc le programme le plus court gagne!
- Vous n'êtes pas autorisé à prendre des commentaires.
- Votre programme doit finalement se terminer de façon déterministe mais vous pouvez supposer que la machine a une mémoire infinie.
- Vous pouvez supposer que le type de numéro de votre langue peut contenir n'importe quelle valeur finie mais devez expliquer comment cela fonctionne exactement dans votre langue (ex: un flotteur a-t-il une précision infinie?)
- Les infinis ne sont pas autorisés en sortie.
- Le dépassement de capacité d'un type de nombre lève une exception. Il ne s'enroule pas.
- Vous devez fournir une explication de la raison pour laquelle votre numéro est si important et une version non golfée de votre code pour vérifier si votre solution est valide (car il n'y a pas d'ordinateur avec suffisamment de mémoire pour stocker le numéro de Loader).
Voici donc une explication du numéro de Loader. Voir http://googology.wikia.com/wiki/Loader%27s_number et les liens qui s'y trouvent pour des détails plus précis. En particulier, il contient un programme qui produit exactement le numéro de Loader (par définition).
Le calcul des constructions est essentiellement un langage de programmation aux propriétés très particulières.
Tout d'abord, chaque programme syntaxiquement valide se termine. Il n'y a pas de boucles infinies. Cela sera très utile, car cela signifie que si nous exécutons un programme de calcul arbitraire de constructions, notre programme ne restera pas bloqué. Le problème est que cela implique que le calcul des constructions n'est pas Turing complet.
Deuxièmement, parmi les langues complètes non-Turing, c'est l'un des plus puissants. Essentiellement, si vous pouvez prouver qu'une machine de Turing s'arrêtera à chaque entrée, vous pouvez programmer une fonction dans le calcul des constructions qui la simulera. (Cela ne rend pas le turing complet, car il existe des machines de turing à l'arrêt dont vous ne pouvez pas prouver qu'elles s'arrêtent.)
Le numéro du chargeur est essentiellement un numéro de castor occupé pour le calcul des constructions, qui est possible à calculer puisque tous les programmes coc se terminent.
En particulier, loader.c définit une fonction appelée D. Approximativement, D(x)itère moins que toutes les chaînes de bits x, les interprète comme des programmes coc, exécute les chaînes syntaxiquement valides et concatène les résultats (qui seront également des chaînes de bits). Il renvoie cette concaténation.
Le numéro du chargeur est D(D(D(D(D(99))))).
Une copie plus lisible du code du wiki de googolologie
int r, a;
P(y,x){return y- ~y<<x;}
Z(x){return r = x % 2 ? 0 : 1 + Z (x / 2 );}
L(x){return x/2 >> Z(x);}
S(v,y,c,t){
int f = L(t);
int x = r;
return f-2 ? f>2 ? f-v ? t-(f>v)*c : y : P(f,P(S(v,y,c,L(x)), S(v+2,t=S(4,13,-4,y),c,Z(x)))) : A(S(v,y,c,L(x)),S(v,y,c,Z(x)));
}
A(y,x){return L(y)-1 ? 5<<P(y,x) : S(4,x,4,Z(r));}
D(x)
{
int f;
int d;
int c=0;
int t=7;
int u=14;
while(x&&D(x-1),(x/=2)%2&&(1)){
d = L(L(D(x))),
f = L(r),
x = L(r),
c - r||(L(u)||L(r)-f||(x/=2)%2&&(u=S(4,d,4, r),t=A(t,d)),f/2&(x/=2)%2&&(c=P(d,c),t=S(4,13,-4,t),u=S(4,13,-4,u))),
c&&(x/=2)%2&&(t=P(~u&2|(x/=2)%2&&(u=1<<P(L(c),u)),P(L(c),t)),c=r)
u/2&(x/=2)%2&&(c=P(t,c),u=S(4,13,-4,t),t=9);
}
return a = P( P( t, P( u, P( x, c)) ),a);
}
main(){return D(D(D(D(D(99)))));}
la source
Réponses:
JavaScript, D ^ 6 (9) (
508501495492487485481 octets)Ceci est un code codé.
Code décodé:
Code décodé et non golfé (les conditions et les trucs sont conservés de loader.c):
En cela, il est supposé être:
NumberNumberAlgorithme d'encodage / décodage:
L'encodage se fait comme suit:
L'algorithme de décodage:
La compression a été effectuée avec ce code , cochez uniquement la dernière case. Étant donné que cela encodera la plus grande sauvegarde en premier, ce n'est pas la compression la plus efficace, mais je ne sais pas non plus comment la rendre plus petite.
JavaScript, (339 caractères )
Ce code prendra la chaîne de 16 bits comme un, la convertira en chaîne de 8 bits avec le même binaire (BE), et
evalce.Le code décodé est le code codé ci-dessus.
Preuve que D ^ 6 (9)> D ^ 5 (99)
Pour cela, nous comparerions D (9) et 99.
En exécutant manuellement le code, D (9) est trouvé égal à
(15*2^14849+1)*2^((15*2^14849+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^929+1)*2^((15*2^929+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^(15*2^59+1)))))))))))))))))))))))))))))))), et même D (0) est égal à8646911284551352321.Donc, D (9) >>> 99, et parce que D est strictement croissant, D ^ 6 (9)> D ^ 5 (99).
D(D(D(D(D(99)))))pourD(D(D(D(D(D(9)))))). Cela a également mélangé les lettres.&&(1)pourD(x)la condition de la boucle de./2s à>>1s carNumberfor...inàfor...of.evalpourD, supprimerreturn.la source
Python 3, D ^ 6 (9) (
608600599 octets)Ceci est un code codé. Extrait:
En cela, il est supposé être:
Il s'agit essentiellement d'un portage de ma réponse JavaScript . Pour plus de détails, vérifiez celui-là.
La compression a été effectuée avec cela .
Je ne connais pas très bien Python, donc il y a certainement des endroits pour économiser des octets.
Je pense que le sous-600 est possible.sous-600 a été prouvé.Spour réduire les parenthèsesu/2dans l'avant-dernière ligne de la définition deDtou>>1, sauver un octet de le compresser en un caractère avec d'autres>>1s.la source
Ruby, D ^ 6 (9) (553 octets)
Ceci est un code codé. Extrait:
Ce code est le numéro du chargeur avec D 6 (9) à la place.
En cela, il est supposé être:
Il s'agit essentiellement d'un portage de ma réponse JavaScript et de ma réponse Python 3 . Pour plus de détails, vérifiez-les.
La compression a été effectuée avec cela (peut apparaître car elle n'existe pas).
Je suis un débutant chez Ruby, donc peut-être moins de 512 est possible, mais j'en doute.
la source