Como acompanhamento do programa de finalização mais curto, cujo tamanho de saída excede o número de Graham e Golf um número maior que o TREE (3) , apresento um novo desafio.
O número do carregador é um número muito grande, difícil de explicar (já que foi o resultado de um exercício de código de golfe com um objetivo flexível). Há uma definição e explicação aqui , mas para fins de auto-contenção, tentarei explicá-lo mais adiante neste post.
O algoritmo que Ralph Loader usou produz um dos maiores números de qualquer algoritmo (computável) já escrito! De fato, o número do Loader é o maior número "computável" no Googology Wiki. (Por número "computável", eles significam um número definido em termos de cálculo.) Isso significa que, se a resposta produzir um número maior que o número do Carregador de uma maneira interessante (ou seja, não apenas o número do Carregador + 1), você poderá descer em História da Googologia! Dito isto, os programas que produzem algo como o número Loader + 1 são respostas e candidatos definitivamente válidos para essa pergunta; só não espere nenhuma fama.
Seu trabalho é criar um programa de encerramento que produza um número maior que o número do Loader. Isso é código-golfe , então o programa mais curto vence!
- Você não tem permissão para receber informações.
- Seu programa deve eventualmente terminar deterministicamente, mas você pode assumir que a máquina possui memória infinita.
- Você pode assumir que o tipo de número do seu idioma pode conter qualquer valor finito, mas precisa explicar como isso funciona exatamente no seu idioma (por exemplo: um flutuador tem precisão infinita?)
- Infinidades não são permitidas como saída.
- O fluxo insuficiente de um tipo de número gera uma exceção. Não envolve.
- Você precisa fornecer uma explicação do motivo pelo qual o seu número é tão grande e uma versão sem código do seu código para verificar se a sua solução é válida (já que não há computador com memória suficiente para armazenar o número do Loader).
Então, aqui está uma explicação do número do carregador. Veja http://googology.wikia.com/wiki/Loader%27s_number e os links para obter detalhes mais precisos. Em particular, ele contém um programa que produz o número do Loader exatamente (por definição).
O cálculo das construções é essencialmente uma linguagem de programação com propriedades muito particulares.
Primeiro de tudo, todo programa sintaticamente válido termina. Não há loops infinitos. Isso será muito útil, pois significa que, se executarmos um programa de cálculo arbitrário de construções, nosso programa não ficará preso. O problema é que isso implica que o cálculo das construções não está completo.
Segundo, entre os idiomas completos não-Turing, é um dos mais poderosos. Essencialmente, se você puder provar que uma máquina de Turing será interrompida em cada entrada, poderá programar uma função no cálculo de construções que a simularão. (Isso não o torna completo, porque existem máquinas de parada que você não pode provar que estão parando.)
O número do carregador é essencialmente um número ocupado do castor para o cálculo das construções, que é possível calcular, pois todos os programas COC terminam.
Em particular, loader.c define uma função chamada D. Aproximadamente, D(x)itera sobre todas as cadeias de bits menores que x, interpreta-as como programas COC, executa as sintaticamente válidas e concatena os resultados (que também serão cadeias de bits ). Retorna essa concatenação.
O número do carregador é D(D(D(D(D(99))))).
Uma cópia mais legível do código do wiki da googolology
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)))));}
fonte
Respostas:
JavaScript, D ^ 6 (9) (
508501495492487485481 bytes)Este é um código codificado.
Código decodificado:
Código decodificado e não destruído (as condições e outras coisas são mantidas no loader.c):
Neste, supõe-se que seja:
NumberNumberAlgoritmo de codificação / decodificação:
A codificação é feita da seguinte maneira:
O algoritmo de decodificação:
A compactação foi feita com esse código , marque apenas a última caixa. Como isso codificará o maior salvamento primeiro, não é a compressão mais eficiente, mas também não sei como diminuí-lo.
JavaScript, (339 caracteres )
Este código pegará a string de 16 bits como a, a converterá em string de 8 bits com o mesmo binário (BE) e
evalele.O código decodificado é o código codificado acima.
Prova de que D ^ 6 (9)> D ^ 5 (99)
Para isso, compararíamos D (9) e 99.
Ao executar o código manualmente, D (9) é encontrado igual a
(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)))))))))))))))))))))))))))))))), e até D (0) é igual a8646911284551352321.Portanto, D (9) >>> 99 e, como D está aumentando estritamente, D ^ 6 (9)> D ^ 5 (99).
D(D(D(D(D(99)))))paraD(D(D(D(D(D(9)))))). Também isso embaralhou as letras.&&(1)paraD(x)'s condição de ciclo./2dos>>1sa porqueNumberfor...inparafor...of.evalparaD, removerreturn.fonte
Python 3, D ^ 6 (9) (
608600599 bytes)Este é um código codificado. Extraído:
Neste, supõe-se que seja:
Esta é basicamente uma porta da minha resposta JavaScript . Para mais detalhes, verifique esse.
A compactação foi feita com isso .
Eu não sou muito experiente em Python, então certamente existem lugares para salvar bytes.
Eu acho que sub-600 é possível.sub-600 foi comprovado.Spara reduzir parêntesesu/2a terceira última linha da definição deDparau>>1, salvando um byte de compactá-lo em um caractere com outros>>1s.fonte
Ruby, D ^ 6 (9) (553 bytes)
Este é um código codificado. Extraído:
Este código é o número do carregador com D 6 (9).
Neste, supõe-se que seja:
Esta é basicamente uma porta da minha resposta JavaScript e Python 3 . Para mais detalhes, verifique-os.
A compactação foi feita com isso (pode parecer que não existe).
Eu sou iniciante no Ruby, então talvez seja possível menos de 512, mas duvido.
fonte