Ecrivez le programme le plus court possible (longueur mesurée en octets) répondant aux exigences suivantes:

• pas d'entrée
• la sortie est sur stdout
• l'exécution se termine finalement
• le nombre total d'octets de sortie dépasse le nombre de Graham

Supposons que les programmes s'exécutent jusqu'à la fin "normale" d'un ordinateur idéal ¹ pouvant accéder à des ressources illimitées et que les langages de programmation courants soient modifiés si nécessaire (sans modification de la syntaxe). En raison de ces hypothèses, nous pourrions appeler cela une sorte d'expérience de Gedanken.

Pour commencer, voici un programme Ruby de 73 octets qui calcule f _{ω + 1} (99) dans la hiérarchie en pleine croissance :

f=proc{|k,n|k>0?n.times{n=f[k-1,n]}:n+=1;n};n=99;n.times{n=f[n,n]};puts n

¹ EDIT: Plus précisément, supposons que nous prenions un système existant et que nous le modifions uniquement pour ne pas avoir de limite maximale de la taille de stockage (mais elle est toujours finie). Les temps d'exécution des instructions ne sont pas supposés être modifiés, mais la machine est supposée être idéale en ce sens qu'elle n'aura pas de limite supérieure de durée de vie.

GolfScript ( 49 47 caractères)

4.,{\):i\.0={.0+.({<}+??\((\+.@<i*\+}{(;}if.}do

Voir Durée de vie d'un ver pour de nombreuses explications. En bref, il imprime un plus grand nombre de f que _{co ^co} (2).

Haskell, _{59 57 55} 63

(f%s)1=s;(f%s)n=f.(f%s)$n-1
main=print$((flip((%3)%(3^))3)%4)66

Comment ça marche: %prend simplement une fonction et la compose n-1fois par dessus s; c'est-à-dire qu'il %3prend une fonction fet retourne une fonction négale à son application fà 3 n-1fois d'affilée. Si nous itérons l'application de cette fonction d'ordre supérieur, nous obtenons une séquence de fonctions à croissance rapide - à commencer par l'exponentiation, c'est exactement la séquence des tailles de Knuth-flèche-forêt:
((%3)%(3^))1 n = (3^)n     = 3ⁿ = 3↑n
((%3)%(3^))2 n = ((3^)%3)n = (3↑)ⁿ⁻¹ $ 3 = 3↑↑n
((%3)%(3^))3 n = (((3^)%3)%3)n = (3↑↑)ⁿ⁻¹ $ 3  = 3↑↑↑n
et ainsi de suite. ((%3)%(3^))n 3est 3 ↑ⁿ 3, qui est ce qui apparaît dans le calcul du nombre de Graham. Il ne reste plus qu'à composer la fonction(\n -> 3 ↑ⁿ 3) ≡ flip((%3)%(3^))3plus de 64 fois, en plus de 4 (le nombre de flèches par lequel commence le calcul), pour obtenir un nombre supérieur à celui de Graham. Il est évident que le logarithme (quelle fonction légèrement lente!) g₆₅Est toujours supérieur à celui-ci g₆₄=G, donc si nous imprimons ce nombre, la longueur de sortie dépasse G.

⬛

Pyth , 29 28 octets

M?*GHgtGtgGtH^ThH=ZTV99=gZTZ

Définit un lambda pour l'hyper-opération et l'appelle de manière récursive. Comme la définition du nombre de Graham, mais avec des valeurs plus grandes.

Cette:

M?*GHgtGtgGtH^3hH

Définit un lambda, à peu près égal au python

g = lambda G, H:
  g(G-1, g(G, H-1)-1) if G*H else 3^(H+1)

Ceci donne la fonction hyper-opération, g (G, H) = 3 ↑ ^{G + 1} (H + 1).
Ainsi, par exemple, g (1,2) = 3 ↑ ² 3 = 7 625 597 484 987, que vous pouvez tester ici .

V<x><y>démarre une boucle qui exécute le corps y, xfois.
=gZTest le corps de la boucle ici, ce qui équivaut àZ=g(Z,10)

Le code:

M?*GHgtGtgGtH^3hH=Z3V64=gZ2)Z

Devrait appeler récursivement l'hyperopération ci-dessus 64 fois, donnant le numéro de Graham.

Dans ma réponse, cependant, j’ai remplacé les chiffres uniques par T, initialisés à 10, et augmenté la profondeur de la récursion à 99. Avec la notation Graham Array , le nombre de Graham est [3,3,4,64], et mon programme affiche le plus grand [10,11,11,99]. J'ai également supprimé le )qui ferme la boucle pour enregistrer un octet, de sorte qu'il imprime chaque valeur successive dans les 99 itérations.

Python (111 + n), n = longueur (x)

Bien que celui-ci ne soit pas aussi court que le programme Ruby du répondeur, je le posterai quand même, pour écarter cette possibilité.

Il utilise la fonction Ackermann et appelle la fonction Ackermann avec m et n étant les valeurs d'un autre appel à la fonction Ackermann, et effectue un retour 1000 fois.

C'est probablement plus grand que le nombre de Graham, mais je ne suis pas sûr, car personne ne connaît la longueur exacte de celui-ci. Il peut être facilement étendu, si ce n’est pas plus grand.

x=999
b='A('*x+'5,5'+')'*x
def A(m,n):n+1 if m==0 else A(m-1,A(m,n-1)if n>0 else 1)
exec('print A('%s,%s')'%(b,b))

Ruby, 54 52 50 octets

f=->b{a*=a;eval"f[b-1];"*b*a};eval"f[a];"*a=99;p a

Ruby, 85 81 76 71 68 64 63 59 57 octets

f=->a,b=-a{eval"a*=b<0?f[a,a]:b<1?a:f[a,b-1];"*a};p f[99]

Hiérarchie à croissance assez rapide avec f (a + 1)> f _{ω + 1} (a).

Ruby, 61 octets

f=->a,b=-a{a<0?9:b==0?a*a:f[f[a-1,b],b>0?b-1:f[a,b+1]]};f[99]

Fondamentalement, une fonction Ackermann avec une torsion.

Ruby, 63 59 octets

n=99;(H=->a{b,*c=a;n.times{b ?H[[b-1]*n*b+c]:n+=n}})[n];p n

Un autre Ruby, 74 71 octets

def f(a,b=a)a<0?b:b<0?f(a-1):f(a-1,f(a,b-1))end;n=99;n.times{n=f n};p n

Ackermann fonctionne à lui seul 99 fois.

Python: 85

f=lambda a,a:a*a
exec'f=lambda a,b,f=f:reduce(f,[a]*b,1)'*99
exec'f('*64+'3'+',3)'*64

Ce qui pourrait peut-être être réduit à 74 +length(X) :

f=lambda a,a:a*a
exec'f=lambda a,b,f=f:reduce(f,[a]*b,1)'*int('9'*X)
f(3,3)

Où Xest un grand nombre approprié, de sorte que l'hyperopération résultante 3, 3soit plus grande que le nombre de Graham (si ce nombre est inférieur à 99999999999alors un octet est enregistré).

Remarque: je suppose que le code python est exécuté sur l'interpréteur interactif; le résultat est donc imprimé sur la sortie standard. Sinon, ajoutez des 9octets à chaque solution pour l'appel à print.

Javascript, 83 octets

Une autre solution de fonction Ackermann.

(function a(m,n,x){return x?a(a(m,n,x-1),n,0):(m?a(m-1,n?a(m,n-1):1):n+1)})(9,9,99)

JavaScript, 68 octets, toutefois incompétent pour utiliser ES6

a=(x,y)=>y?x?a(a(x-1,y)*9,y-1):a(9,y-1):x;b=x=>x?a(9,b(x-1)):9;b(99)

a la fonction est similaire à la notation en flèche vers le haut avec la base 9.

       /a(a(x-1,y)*9,y-1)  x>0, y>0
a(x,y)=|a(9,y-1)           x=0, y>0
       \x                  y=0

bla fonction est: b (x) = b ^x (9).

b(99)est ~ f _{ω + 1} (99), par rapport au nombre de Graham <f _{ω + 1} (64).