É hora de encarar a verdade: não estaremos aqui para sempre, mas pelo menos podemos escrever um programa que sobreviverá à raça humana, mesmo que ela lute até o fim dos tempos.

Sua tarefa é escrever um programa que tenha um tempo de execução esperado maior que o tempo restante até o fim do universo.

Você pode assumir que:

• O universo morrerá de entropia em 10 ^mil anos.
• O seu computador:
  • Sobreviverá ao universo, porque é feito de Unobtainium .
  • Possui limite infinito de memória / pilha / recursão.
  • Seu processador possui velocidade limitada.

Você deve mostrar que o seu programa termina (desculpe, não há loops infinitos) e calcular o tempo de execução esperado.

As brechas padrão se aplicam.

Esse é um desafio de código de golfe, portanto o código mais curto que satisfaz os critérios vence.

EDIT :

Infelizmente, verificou-se (30 minutos depois) que o campo de improbabilidade do Unobtainium interfere com o relógio interno do computador, tornando-o inútil. Portanto, os programas baseados no tempo são interrompidos imediatamente. (Quem deixaria um programa que apenas espera como seu legado, afinal?).

O processador do computador é semelhante ao Intel i7-4578U; portanto, uma maneira de medir o tempo de execução é executar o programa em um computador semelhante com uma entrada menor (espero) e extrapolar o tempo de execução.

Pódio

#CharsLanguageUpvotes        Author        
1    5      CJam              20       Dennis                  
2    5      J                      5         algorithmshark      
3    7      GolfScript       30       Peter Taylor          
4    9     Python             39       xnor                      
5    10   Matlab             5         SchighSchagh      

_{* Upvotes em 31/08}

CJam, 5 bytes

0{)}h

Como funciona

 0   " Push 0.                                 ";
 {   "                                         ";
   ) " Increment the Big Integer on the stack. ";
 }h  " Repeat if the value is non-zero.        ";

Este programa será interrompido quando o heap não puder mais armazenar o Big Inteiro, o que não acontecerá tão cedo em um computador desktop moderno.

O tamanho padrão da pilha é de 4.179.623.936 bytes no meu computador (Java 8 no Fedora). Como pode ser aumentado para um valor arbitrário -Xmx, o único limite real é a memória principal disponível.

Hora da morte

Supondo que o intérprete precise de x bits de memória para armazenar um Inteiro Grande não negativo menor que 2 ^x , temos que contar até 2 ^{8 × 4,179,623,936} = 2 ^{33,436,991,488} . Com um incremento por ciclo de clock e meu Core i7-3770 (3,9 GHz com turbo), isso levará 2 ^{33.436.991.488} ÷ 3.400.000.000> 10 ^{10.065.537.393} segundos, ou seja, mais de 10 ^{10.065.537.385} anos.

JavaScript, 39

(function f(x){for(;x!=++x;)f(x+1)})(0)

Explicação

Como o JavaScript não representa precisamente números inteiros grandes, o loop for(;x!=++x;)termina uma vez que é xatingido 9007199254740992.

O corpo do loop for será executado Fib(9007199254740992) - 1vezes, onde Fib(n)é o enésimo número de fibonacci.

Nos testes, sei que meu computador fará menos de 150.000 iterações por segundo. Na realidade, seria muito mais lento porque a pilha aumentaria muito.

Assim, o programa levará pelo menos (Fib(9007199254740992) - 1) / 150000segundos para ser executado. Não consegui calcular Fib(9007199254740992)porque é muito grande, mas sei que é muito maior que 10 ¹⁰⁰⁰ * 150.000.

EDIT: Como observado nos comentários, Fib(9007199254740992)é aproximadamente 4,4092 * 10 ^{1882393317509686} , o que é realmente grande o suficiente.

Python (9)

9**9**1e9

Isso tem mais de 10 ** 10000000 bits, portanto, a computação deve nos levar muito além da morte por calor.

Eu verifiquei que isso leva cada vez mais tempo para valores maiores, mas ainda razoáveis, para que não seja apenas otimizado pelo intérprete.

Edit: Jogou dois caracteres ao remover parênteses graças a @ user2357112. Até que Python trata expoentes sucessivos como uma torre de energia.

GolfScript ( 12 caracteres)

9,{\?}*

Isso calcula e imprime 8 ^ 7 ^ 6 ^ 5 ^ 4 ^ 3 ^ 2 ~ = 10 ^ 10 ^ 10 ^ 10 ^ 183230. Para imprimi-lo (não importa o cálculo) em 10 ^ 1000 anos ~ = 10 ^ 1007,5 segundos, ele precisa imprimir cerca de 10 ^ (10 ^ 10 ^ 10 ^ 183230 - 10 ^ 3) dígitos por segundo.

Marbelous 68 66 bytes

}0
--@2
@2/\=0MB
}0@1\/
&0/\>0!!
--
@1
00@0
--/\=0
\\@0&0

Marbelous é uma linguagem de 8 bits com valores representados apenas por bolas de gude em uma máquina semelhante ao Rube Goldberg, portanto, isso não foi muito fácil. Essa abordagem é aproximadamente equivalente ao seguinte pseudocódigo:

function recursiveFunction(int i)
{
    for(int j = i*512; j > 0; j--)
    {
        recursiveFunction(i - 1);
    }
}

como o valor máximo é 256, (representado por 0 no programa Marbleous, que é tratado de maneira diferente em lugares diferentes), recursiveFunction (1) será chamado de um total 256!*512^256igual a 10^1200, fácil o suficiente para sobreviver ao universo.

O Marbelous não tem um intérprete muito rápido, parece que pode executar 10^11chamadas dessa função por ano, o que significa que estamos olhando para um tempo de execução de 10^1189anos.

Mais explicações sobre o conselho da Marbelous

00@0
--/\=0
\\@0&0

00é um literal de linguagem (ou mármore), representado em hexadecimal (então 0). Esse mármore cai sobre o --, que diminui qualquer mármore em 1 (00 envolve e se transforma em FF ou 255 em decimal). O Marble agora com o valor FF cai sobre o \\que empurra uma coluna para a direita, para a inferior @0. Este é um portal e teleporta o mármore para o outro @0dispositivo. Lá, o mármore pousa no /\dispositivo, que é um duplicador, coloca uma cópia do mármore --à sua esquerda (este mármore continuará girando entre os portais e será diminuído a cada ciclo) e um =0à sua direita.=0compara o mármore com o valor zero e deixa o mármore cair se for igual e empurra para a direita, se não for. Se o mármore tem o valor 0, ele cai em &0um sincronizador, que explicarei mais adiante.

Em suma, isso apenas começa com um valor de 0 em um loop e o diminui até atingir 0 novamente, depois coloca esse valor em um sincronizador e continua em loop ao mesmo tempo.

}0@1
&0/\>0!!
--
@1

}0é um dispositivo de entrada, inicialmente a enésima (linha 0) entrada de linha de comando ao chamar o programa é colocada em todos os }ndispositivos. Portanto, se você chamar esse programa com a entrada de linha de comando 2, um valor de mármore 02 substituirá isso }0. Esse mármore então cai no &0dispositivo, outro sincronizador e os &nsincronizadores mantêm mármores até que todos os outros correspondentes também &nsejam arquivados. O mármore então é diminuído, teleportado e duplicado, como no loop explicado anteriormente. A cópia correta é verificada quanto à desigualdade com zero ( >0) se não for 0, ela falha. Se for 0, é empurrado para a direita e cai !!, o que encerra o tabuleiro.

Ok, até agora temos um loop que conta continuamente de 255 a 0 e permite que outro loop semelhante (alimentado pela entrada da linha de comando) seja executado uma vez toda vez que atingir 0. Quando esse segundo loop for executado n vezes (máximo sendo 256 ) o programa termina. Portanto, são 65536 execuções no loop. Não é o suficiente para sobreviver ao universo.

}0
--@2
@2/\=0MB

Isso deve começar a parecer familiar, a entrada é decrementada uma vez e, em seguida, esse valor circula e é copiado (observe que o mármore só é diminuído uma vez, não em todas as execuções do loop). Em seguida, é verificado se a igualdade é igual a 0 e, se não for zero, aterrissará MB. Esta é uma função no Marbelous, todo arquivo pode conter várias placas e cada placa é uma função, todas as funções devem ser nomeadas precedendo a grade por :[name]. Todas as funções, exceto a primeira função no arquivo, que possui um nome padrão: MB. Portanto, esse loop chama continuamente a placa principal novamente com um valor em n - 1que n é o valor com o qual essa instância da função foi chamada.

Então porque n*512?

Bem, o primeiro loop é executado em 4 ticks (e 256 vezes) e o segundo loop é executado n vezes antes de a placa terminar. Isso significa que o fórum corre cerca de n*4*256ticks. O último loop (que executa a chamada da função recursiva) é compactador e é executado em 2 ticks, o que significa que ele consegue chamar os n*4*256/2 = n*512tempos da função .

Quais são os símbolos que você não mencionou?

\/ é uma lixeira, que remove bolinhas de gude do tabuleiro, isso garante que as bolinhas descartadas não interfiram com outras bolinhas que estão dando voltas e impedem que o programa seja encerrado.

Bônus

Como as bolinhas de gude que caem na parte inferior de uma placa maravilhosa são enviadas para STDOUT, esse programa imprime uma infinidade de caracteres ASCII enquanto é executado.

Perl, 66 58 caracteres

sub A{($m,$n)=@_;$m?A($m-1,$n?A($m,$n-1):1):$n+1;}A(9,9);

O acima é uma implementação da função Ackermann – Péter . Não tenho idéia do tamanho de A (9,9), mas tenho certeza de que levará um tempo surpreendentemente longo para avaliar.

MATLAB, 58 52 caracteres

Precisamos de pelo menos uma solução aritmética de precisão finita, portanto:

y=ones(1,999);while y*y',y=mod(y+1,primes(7910));end

x = ones (1.999); y = x; enquanto qualquer (y), y = mod (y + x, primos (7910)); end

( com agradecimentos a @DennisJaheruddin por derrubar 6 caracteres )

O número de ciclos necessários para concluir é dado pelo produto dos primeiros 999 primos. Como a grande maioria deles tem mais de 10 anos, o tempo necessário para realizar a convergência seria centenas ou milhares de ordens de magnitude maiores que o limite de tempo mínimo.

Mathematica, 25 19 bytes

Esta solução foi lançada antes das funções de tempo serem desqualificadas.

While[TimeUsed[]<10^10^5]

TimeUsed[]retorna os segundos desde o início da sessão e o Mathematica usa tipos de precisão arbitrária. Há cerca de 10 a ⁷ segundos em um ano, portanto, esperar 10 ¹⁰⁰⁰⁰ segundos deve ser suficiente.

Alternativa mais curta / mais simples (/ válida):

For[i=0,++i<9^9^9,]

Vamos apenas contar. Teremos que contar um pouco mais, porque podemos fazer muitos incrementos em um segundo, mas o limite mais alto não custa caracteres.

Tecnicamente, nas duas soluções, eu poderia usar um limite muito mais baixo porque o problema não especifica uma velocidade mínima do processador.

Python 3-49

Isso faz algo útil: calcula Pi com precisão sem precedentes usando a série infinita de Gregory-Leibniz.

Apenas no caso de você estar se perguntando, este programa repetirá os 10**10**10**2.004302604952323tempos.

sum([4/(i*2+1)*-1**i for i in range(1e99**1e99)])

Precisão arbitrária: 78

from decimal import*
sum([Decimal(4/(i*2+1)*-1**i)for i in range(1e99**1e99)])

Fonte da imagem

A Respiração Terminal

Devido aos enormes cálculos que ocorrem, as 1e99**1e99iterações demoram menos de 1e99**1e99anos. Agora, (1e99**1e99)-1e1000quase não faz diferença. Isso significa que esse programa será executado por muito mais tempo do que a morte do nosso universo.

Renascimento

Agora, os cientistas propõem que 10**10**56 years, dentro , o universo renascerá devido a flutuações quânticas ou tunelamento. Então, se cada universo é exatamente o mesmo, por quantos universos meu programa viverá?

(1e99**1e99)/(1e10+1e1000+10**10**56)=1e9701

Assumindo que o universo sempre viverá 1e10+1e1000anos e levará 10**10**56anos para 'reiniciar', meu programa viverá através de 1e9701universos. Isso pressupõe, é claro, que a unobtainium possa sobreviver ao Big Bang.

Python 59 (funciona na maioria das vezes)

Não pude resistir

from random import*
while sum(random()for i in range(99)):0

Embora seja verdade que isso teoricamente poderia terminar em menos de um milissegundo, o tempo de execução médio é bem superior 10^400ao tempo de vida útil especificado do universo. Obrigado a @BetaDecay, @undergroundmonorail e @DaboRoss por reduzirem 17 caracteres aproximadamente.

J - 5 caracteres, acho

Observe que todos os itens a seguir estão em aritmética de precisão arbitrária, porque o número 9 sempre tem um pouco xao lado.

Em sete caracteres, temos !^:!!9x, que é como correr

n = 9!
for i in range(n!):
    n = n!

em aritmética de precisão arbitrária. Definitivamente, isso está acima do limite, porque a Synthetica disse isso , então temos um limite superior.

Em seis caracteres, também podemos escrever ^/i.9x, que calcula todos os resultados intermediários de 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8. Wolfram | Alpha diz que 2^3^4^5^6^7^8é aproximadamente 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 6.65185, o que provavelmente também limpa a inspeção.

Também temos o caractere cinco!!!9x , que é apenas ((9!)!) !. W | A diz que é 10 ^ 10 ^ 10 ^ 6.2695, que ainda deve ser grande o suficiente ... Isso é como 1.6097e1859933dígitos -ish, que é decididamente maior que 3.154e1016o número de nanossegundos no universo, mas eu admito que não tenho idéia de como alguém pode descobrir os reais tempos de execução dessas coisas.

A impressão por si só deve demorar o suficiente para durar mais do que o universo; portanto, deve ficar bem.

C, 63 56 caracteres

f(x,y){return x?f(x-1,y?f(x,y-1):1):y+1;}main(){f(9,9);}

Isso é baseado na idéia de um cara chamado Wilhelm. Minha única contribuição é condensar o código nesta parte curta (e ilegível).

Provar que termina é feito por indução.

• Se x é 0, ele termina imediatamente.
• Se termina para x-1 e qualquer y, também termina para x, isso pode ser mostrado por indução.

Provando a indução passo a passo:

• Se y é 0, há apenas uma chamada recursiva com x-1, que termina por suposição de indução.
• Se f (x, y-1) termina, então f (x, y) também termina porque a chamada mais interna de f é exatamente f (x, y-1) e a chamada mais externa termina de acordo com a hipótese de indução.

O tempo de execução esperado é de A (9,9) / 11837 segundos. Esse número tem mais dígitos que o número de quarks no universo observável.

Matlab ( 10 8 caracteres)

1:9e1016

IMHO, a maioria das entradas está se esforçando demais ao computar coisas grandes e complicadas. Esse código simplesmente inicializa uma matriz de 9x10 ¹⁰¹⁶ double s, contando de 1, que ocupa 7,2x10 ^ ¹⁰¹⁷ bytes. Em uma CPU moderna com uma largura de banda de memória máxima de 21 GB / s ou 6,63x10 ^ ¹⁷ bytes / ano , serão necessários pelo menos 1,09x10 ¹⁰⁰⁰ anos para inicializar o array, e muito menos tentar imprimi-lo, pois eu não me incomodei. suprimindo a saída com um ponto e vírgula à direita. (;

soluções antigas

nan(3e508)

alternativamente

inf(3e508)

Esse código simplesmente criará uma matriz quadrada de NaNs / infinitos de tamanho 3e508x 3e508 = 9e1016dobras de 8 bytes ou 7.2e1017bytes.

Perl, 16 caracteres

/$_^/for'.*'x1e9

Isso cria uma string repetindo ". *" Um bilhão de vezes e depois a usa como agulha e palheiro em uma correspondência de regex. Por sua vez, isso faz com que o mecanismo regex tente todas as partições possíveis de uma sequência de dois bilhões de caracteres. De acordo com esta fórmula da Wikipedia , existem cerca de 10 ³⁵²¹⁸ dessas partições.

A solução acima tem 16 caracteres, mas requer apenas cerca de 2 GB de memória, o que significa que pode ser executada em um computador real. Se assumirmos memória infinita e tamanho finito de registro (o que provavelmente não faz sentido), ele pode ser reduzido para 15 caracteres enquanto aumenta drasticamente o tempo de execução:

/$_^/for'.*'x~0

(Eu não testei, mas acho que poderia funcionar com um Perl de 32 bits criado em uma máquina de 64 bits com pelo menos 6 GB de RAM.)

Notas:

• x é o operador de repetição de string.
• o forloop não é real; é usado apenas para salvar um caractere (comparado a $_=".*"x1e9;/$_^/).
• a final ^na regex garante que apenas a sequência vazia possa corresponder; como os quantificadores de regex são gananciosos por padrão, esta é a última coisa que o mecanismo tentará.
• os benchmarks no meu computador para valores (1..13) sugerem que o tempo de execução é realmente O (exp (n)), que é ainda mais do que O (exp (sqrt (n))) na fórmula da Wikipedia.

J (12)

(!^:(!!9))9x

O que isso se resume em Python (assumindo que !funciona):

a = 9 
for i in range((9!)!):
    a = a!

EDITAR:

Bem, o programa pode levar, no máximo, 2 × 10^-1858926segundos por ciclo, para ser concluído dentro do tempo necessário. Dica: isso nem funciona no primeiro ciclo, não importa o último;).

Além disso: este programa pode precisar de mais memória do que a entropia no universo ...

C # 217

Não sou muito jogador de golfe, mas não pude resistir à função de Ackerman . Também não sei como calcular o tempo de execução, mas ele definitivamente será interrompido e, com certeza, será executado por mais tempo que esta versão .

class P{
static void Main(){for(int i=0;i<100;i++){for(int j=0;j<100;j++){Console.WriteLine(ack(i,j));}}}
static int ack(int m,int n){if (m==0) return n+1;if (n ==0) return ack(m-1,1);return ack(m-1,ack(m,n-1));}
}

Primeira tentativa de código de golfe, mas aqui vai.

VBA - 57 45

x=0
do
if rnd()*rnd()<>0 then x=0
x=x+1
while 1=1

Portanto, o X aumentará um ponto se ocorrer um evento 1 em 2 ^ 128 e redefinirá se não ocorrer. O código termina quando esse evento acontece 2 ^ 64 + 1 vezes seguidas. Não sei como começar a calcular o tempo, mas acho que é enorme.

EDIT: Eu elaborei a matemática e a probabilidade de isso acontecer em cada loop é de 1 em 2 ^ 128 ^ (1 + 2 ^ 64), que tem cerca de 20000 dígitos. Supondo que 1000000 loops / s (estimativa de número insuficiente) e 30000000 s / ano são 3 * 10 ^ 13 ciclos por ano, 10 ^ 1000 anos restantes são 3 * 10 ^ 1013 ciclos, portanto, isso provavelmente duraria cerca de 20 vezes a tempo restante restante no universo. Fico feliz que minha matemática apóie minha intuição.

C, 30 caracteres

main(i){++i&&main(i)+main(i);}

Supondo que o excesso de sinal assinado por dois de elogios e as entradas de 32 bits, ele será executado por cerca de 2 ^{2 32} chamadas de função, o que deve levar bastante tempo para o universo terminar.

GolfScript, 13 caracteres

0{).`,9.?<}do

Este programa conta apenas de 0 a 10 ^{9 9 −1} = 10 ^387420488 . Supondo, otimista, que o computador funcione a 100 GHz e possa executar cada iteração do programa em um único ciclo, o programa será executado por 10 ^{9 9 a 12} segundos ou cerca de 3 × 10 ^{9 9 a 20} = 3 × 10 ^387420469 anos.

Para testar o programa, você pode substituir o 9por a 2, o que fará com que ele pare em 10 ^{2 2 −1} = 10 ³ = 1000. (Usar um em 3vez de a 2fará com que pare em 10 ^{3 3 −1} = 10 ²⁶ , o que , mesmo com as premissas otimistas acima, ele não será alcançado por pelo menos alguns milhões de anos.)

Autohotkey 37

loop {
if (x+=1)>10^100000000
break
}

Haskell, 23

main=interact$take$2^30

Este programa termina após a leitura de 1073741824 caracteres de stdin. Se for executado sem canalizar nenhum dado stdin, você precisará digitar esse número de caracteres no teclado. Supondo que o teclado tenha 105 teclas, cada uma classificada para 100k ciclos mecânicos e programada para gerar pressionamentos de tecla não mortos, a repetição automática está desativada e o soquete do teclado permite 100 ciclos de conexão, o que fornece o número máximo de pressionamentos de teclas por tempo de atividade do computador de 1050000000, o que é não é suficiente para o programa terminar.

Portanto, o programa será encerrado apenas quando um hardware melhor estiver disponível em termos de número de ciclos, o que efetivamente nunca ocorre neste universo em execução. Talvez da próxima vez, quando a qualidade tiver maior prioridade que a quantidade. Até então, este programa termina em princípio, mas não na prática.

~ ATH, 56

Na linguagem fictícia ~ ATH :

import universe U;
~ATH(U) {
} EXECUTE(NULL);
THIS.DIE()

~ ATH é uma linguagem insuportável para se trabalhar. Sua lógica é composta de nada além de loops infinitos, ou, na melhor das hipóteses, loops de construção efetivamente interminável.

O que muitos codificadores ~ ATH fazem é importar construções finitas e vincular os loops à sua vida útil. Por exemplo, o loop principal aqui terminará com a morte do universo, rotulado como U. Dessa forma, você só precisa esperar bilhões de anos para que ele termine em vez de para sempre.

Peço desculpas pelas violações das brechas fronteiriças; Eu pensei que era muito relevante para deixar passar.

Se alguém realmente se divertiu com isso, mais detalhes: (1) , (2) , (3) , (4)

Rubi (34)

A linha ([0]*9).permutation.each{print}leva cerca de 2,47 segundos para 9! imprime na minha máquina, enquanto a linha ([0]*10).permutation.each{print}leva cerca de 24,7 segundos por 10! imprime, então acho que posso extrapolar aqui e calcular (24.7/10!)*470! seconds in yearsqual é 6,87 * 10 ^ 1040, que deve ser o tempo de execução de:

([0]*470).permutation.each{print}

JavaScript 68 62 caracteres

(function a(m,n){return m==0?n+1:a(m-1,n==0?1:a(m,n-1))})(5,1)

Isso usa a função Ackermann, que pode ser escrita como

function ackermann(a, b) {
  if (a == 0) return b + 1;
  if (b == 0) return ackermann(a-1, 1);
  else return ackermann(a-1, ackermann(a, b-1));
}

Seu tempo de execução aumenta exponencialmente e, portanto, leva muito tempo para calcular. Mesmo que não seja inglês aqui, você pode obter uma visão geral de seus valores de retorno. De acordo com a tabela ackermann(5,1)é igual a 2↑↑(65533)-3, você sabe, muito grande.

Befunge '93 - 40 bytes

(Programa 20x2)

v<<<<<<<<<<<<<<<<<<<
>??????????????????@

Este programa depende de números aleatórios para atrasar. Como os intérpretes da Befunge são bastante lentos, este programa deve atender à demanda. E se não, podemos sempre expandi-lo horizontalmente. Não sei exatamente como calcular o tempo de execução esperado deste programa, mas sei que cada um deles? tem 50/50 de chance de começar de novo ou alterar sua posição horizontal por 1. Existem 18? Eu acho que deveria ser algo parecido com (18 ^ 2) !, que a calculadora do Google diz ser "Infinito"

EDIT: Opa, eu não percebi a outra resposta do Befunge, este é o meu primeiro post aqui. Desculpa.

APL, 10

Eu não acho que essa seja uma resposta válida (pois não é determinística), mas de qualquer maneira ......

{?⍨1e9}⍣≡1

Este programa calcula uma permutação aleatória de 1e9 números ( ?⍨1e9) e se repete até duas saídas consecutivas serem iguais ( ⍣≡)

Portanto, toda vez que uma permutação é calculada, ela tem 1 em 1000000000! chance de terminar. E 1000000000! é pelo menos 10 ^{10 8} .

O tempo necessário para calcular uma permutação é irrelevante pela massa de 1000000000 !. Mas alguns testes mostram que isso é O(n)e extrapolar dá cerca de 30 segundos.

No entanto, meu intérprete se recusa a receber entradas para a função aleatória maior que 2 ³¹ -1 (então usei 1e9) e a geração de permutações de 1000000000 números deu um erro total ao espaço de trabalho. No entanto, conceitualmente, isso pode ser feito com um intérprete APL ideal com memória infinita.

Isso nos leva à possibilidade de usar 2 ⁶³ -1 no lugar de 1e9 para aumentar o tempo de execução para pelo menos 10 ^{10 20} , assumindo uma arquitetura de 64 bits.

Mas espere, a arquitetura é relevante em um intérprete ideal? Inferno não, então não há realmente nenhum limite superior no tempo de execução !!

R, 45 bytes

(f=function(x)if(x)f(x-1)+f(x-1)else 0)(9999)

É um tópico antigo, mas não vejo resposta R, e não podemos ter isso!

O tempo de execução para mim foi de 1s quando x tinha 20 anos, sugerindo um tempo de execução de 2 ^ 9979 segundos.

Se você substituir o zero por um, a saída será 2 ^ x, mas, como está, a saída será zero, seja qual for o x (evita problemas de estouro).

Javascript, 120 bytes

a=[0];while(a.length<1e4)(function(){var b=0;while(b<a.length){a[b]=(a[b]+1)%9;if(a[b])return;b++}a.push(1)})();alert(a)

Pode ser feito com memória mínima (provavelmente menos de meio megabyte), mas leva (provavelmente) cerca de 10 ^8.750 anos para ser interrompido.

Incrementa repetidamente um BigInteger base-9 little-endian até atingir 9 ^{10 4 -1} .

Python 3, 191 bytes

from random import*
r=randint
f=lambda n:2if n<2else f(n-1)
x=9E999
s=x**x
for i in range(f(x)**f(s)):
 while exec(("r(0,f(x**i))+"*int(f(x)))+"r(0,f(x**i))")!=0:
  s=f(x**s)
  print(s)

Primeiro, f é uma função fatorial recursiva e ultra lenta. Em seguida, há 9 * 10⁹⁹⁹ em si, o que gera um OverflowError, mas isso não acontece neste computador Unobtanium. O For-Loop itera 9E999! ^ (9E999 ^ 9E999)! vezes e só vai para a próxima iteração, se 9E999! +1 ints aleatórias entre 0 e 9E99 * ^ i! são todos 0 e em cada iteração do loop while é definido como (9E999 ^ s) !. Esqueci que a impressão de s leva muuuuccchhhhh ...
sei que não é a solução mais curta, mas acho que é realmente eficaz. Alguém pode me ajudar a calcular o tempo de execução?

Máquina de Turing, mas muito pior , 167 bytes

0 0 1 1 2 0 0
1 0 1 0 4 0 0
0 1 1 1 2 0 0
1 1 1 1 5 0 0
0 2 1 0 3 0 0
1 2 0 1 1 0 0
0 3 1 1 4 0 0
1 3 0 0 2 0 0
0 4 1 0 0 0 0
1 4 0 1 3 0 0
0 5 1 0 6 0 1
1 5 1 1 2 0 0

Experimente online!

Deve executar o Busy Beaver de 6 estados e 2 símbolos na página da Wikipedia .

$7.412 \times 10^{36534}$