Escreva o programa mais curto possível (comprimento medido em bytes) atendendo aos seguintes requisitos:

• sem entrada
• saída é stdout
• a execução termina eventualmente
• o número total de bytes de saída excede o número de Graham

Suponha que os programas sejam executados até a finalização "normal" em um computador ideal ¹ capaz de acessar recursos ilimitados e que as linguagens de programação comuns sejam modificadas, se necessário (sem alterar a sintaxe) para permitir isso. Devido a essas suposições, podemos chamar isso de uma espécie de experiência Gedanken.

Para começar, aqui está um programa Ruby de 73 bytes que calcula f _{ω + 1} (99) na hierarquia de rápido crescimento :

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: Mais precisamente, suponha que estamos pegando um sistema existente e modificando-o apenas para não ter limite superior no tamanho do armazenamento (mas é sempre finito). Os tempos de execução das instruções não devem ser modificados, mas presume-se que a máquina seja ideal, pois não terá limite superior na vida útil de operação.

GolfScript ( 49 47 caracteres)

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

Veja a vida de um verme para muitas explicações. Em resumo, isso imprime um número maior que f _{ω ^ω} (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

Como funciona: %simplesmente pega uma função e a compõe várias n-1vezes s; isto é, %3pega uma função fe retorna uma função nigual a aplicá-la fa 3, n-1vezes seguidas. Se iterarmos a aplicação dessa função de ordem superior, obteremos uma sequência de funções que cresce rapidamente - começando pela exponenciação, é exatamente a sequência dos tamanhos de floresta de flechas de Knuth:
((%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
e assim por diante. ((%3)%(3^))n 3é 3 ↑ⁿ 3, que é o que aparece no cálculo do número de Graham. Tudo o que resta a fazer é compor a função(\n -> 3 ↑ⁿ 3) ≡ flip((%3)%(3^))3mais de 64 vezes, além de 4 (o número de setas com o qual o cálculo começa), para obter um número maior que o número de Graham. É óbvio que o logaritmo (que função é muito lenta!) De g₆₅ainda é maior que g₆₄=G, portanto, se imprimirmos esse número, o comprimento da saída excederá G.

⬛

Pitão , 29 28 bytes

M?*GHgtGtgGtH^ThH=ZTV99=gZTZ

Define um lambda para hiperoperação e o chama recursivamente. Como a definição para o número de Graham, mas com valores maiores.

Este:

M?*GHgtGtgGtH^3hH

Define um lambda, aproximadamente igual ao python

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

Isso fornece a função de hiperoperação, g (G, H) = 3 ↑ ^{G + 1} (H + 1).
Então, por exemplo, g (1,2) = 3 ↑ ² 3 = 7.625.597.484.987, que você pode testar aqui .

V<x><y>inicia um ciclo que executa o corpo, y, xvezes.
=gZTé o corpo do loop aqui, que é equivalente aZ=g(Z,10)

O código:

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

Deve recursivamente chamar a hiperoperação acima de 64 vezes, fornecendo o Número de Graham.

Na minha resposta, no entanto, substituí os dígitos únicos com T, inicializados em 10, e aumentei a profundidade da recursão para 99. Usando a Notação Graham Array , o Número de Graham é [3,3,4,64] e meu o programa gera o maior [10,11,11,99]. Também removi o )que fecha o loop para salvar um byte, para que ele imprima cada valor sucessivo nas 99 iterações.

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

Embora este não seja tão curto quanto o programa Ruby do respondente, eu o publicarei de qualquer maneira, para descartar essa possibilidade.

Ele usa a função Ackermann e chama a função Ackermann com m e n sendo os valores de outra chamada para a função Ackermann, e se repete 1000 vezes.

Provavelmente é maior que o número de Graham, mas não tenho certeza, porque ninguém sabe o tamanho exato. Pode ser facilmente estendido, se não for maior.

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 bytes

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

Rubi, 85 81 76 71 68 64 63 59 57 bytes

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

Hierarquia em rápido crescimento com f (a + 1)> f _{ω + 1} (a).

Ruby, 61 bytes

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]

Basicamente, uma função de Ackermann com uma torção.

Ruby, 63 59 bytes

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

Outro Ruby, 74 71 bytes

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

Basicamente, Ackermann funciona 99 vezes.

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

Que talvez pudesse ser reduzido para 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)

Onde X existe um número grande apropriado, de modo que a hiperoperação resultante 3, 3seja maior que o número de Grahams (se esse número for menor do que 99999999999algum byte será salvo).

Nota: Presumo que o código python seja executado no interpretador interativo, portanto, o resultado será impresso em stdout; caso contrário, adicione 9bytes a cada solução para a qual a chamada será feita print.

Javascript, 83 bytes

Outra solução da função 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 bytes, porém pouco atraente para usar o 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 A função é semelhante à notação de seta para cima na 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

ba função é: b (x) = b ^x (9).

b(99)é ~ f _{ω + 1} (99), comparado ao número de Graham <f _{ω + 1} (64).