Es hora de enfrentar la verdad: no estaremos aquí para siempre, pero al menos podemos escribir un programa que sobrevivirá a la raza humana, incluso si lucha hasta el final de los tiempos.

Su tarea es escribir un programa que tenga un tiempo de ejecución esperado mayor que el tiempo restante hasta el final del universo.

Puede suponer que:

• El universo morirá de entropía en 10 ¹⁰⁰⁰ años.
• Tu computadora:
  • Sobrevivirá al universo, porque está hecho de Unobtainium .
  • Tiene memoria infinita / pila / límite de recursión.
  • Su procesador tiene velocidad limitada.

Debe mostrar que su programa finaliza (lo siento, no hay bucles infinitos) y calcular su tiempo de ejecución esperado.

Se aplican las lagunas estándar .

Este es un desafío de código de golf, por lo que gana el código más corto que satisfaga los criterios.

EDITAR :

Desafortunadamente, se descubrió (30 minutos después) que el campo de improbabilidad de Unobtainium interfiere con el reloj interno de la computadora, haciéndolo inútil. Por lo tanto, los programas basados ​​en el tiempo se detienen de inmediato. (¿Quién dejaría un programa que solo espera como su legado vivo, de todos modos?).

El procesador de la computadora es similar al Intel i7-4578U, por lo que una forma de medir el tiempo de ejecución es ejecutar su programa en una computadora similar con una entrada más pequeña (espero) y extrapolar su tiempo de ejecución.

Podio

#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      

_{* Votos a favor el 31/08}

CJam, 5 bytes

0{)}h

Cómo funciona

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

Este programa se detendrá cuando el montón ya no pueda almacenar el Big Integer, lo que no sucederá pronto en una computadora de escritorio moderna.

El tamaño de almacenamiento dinámico predeterminado es 4,179,623,936 bytes en mi computadora (Java 8 en Fedora). Se puede aumentar a un valor arbitrario con -Xmx, por lo que el único límite real es la memoria principal disponible.

Hora de la muerte

Suponiendo que el intérprete necesita x bits de memoria para almacenar un Big Integer no negativo menor que 2 ^x , tenemos que contar hasta 2 ^{8 × 4,179,623,936} = 2 ^{33,436,991,488} . Con un incremento por ciclo de reloj y mi Core i7-3770 (3.9 GHz con turbo), esto tomará 2 ^{33,436,991,488} ÷ 3,400,000,000> 10 ^{10,065,537,393} segundos, que es más de 10 ^{10,065,537,385} años.

JavaScript, 39

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

Explicación

Dado que JavaScript no representa con precisión enteros grandes, el ciclo for(;x!=++x;)termina una vez que xllega 9007199254740992.

El cuerpo del bucle for se ejecutará Fib(9007199254740992) - 1veces, donde Fib(n)es el enésimo número de Fibonacci.

De las pruebas, sé que mi computadora hará menos de 150,000 iteraciones por segundo. En realidad, correría mucho más lento porque la pila crecería mucho.

Por lo tanto, el programa tardará al menos (Fib(9007199254740992) - 1) / 150000segundos en ejecutarse. No he podido calcular Fib(9007199254740992)porque es muy grande, pero sé que es mucho más grande que 10 ¹⁰⁰⁰ * 150,000.

EDITAR: Como se señaló en los comentarios, Fib(9007199254740992)es aproximadamente 4.4092 * 10 ^{1882393317509686} , que de hecho es lo suficientemente grande.

Pitón (9)

9**9**1e9

Esto tiene más de 10 ** 10000000 bits, por lo que calcularlo debería llevarnos mucho más allá de la muerte por calor.

Verifiqué que esto toma más y más tiempo para valores más grandes pero aún razonables, por lo que no solo está siendo optimizado por el intérprete.

Editar: Golfé dos caracteres eliminando parens gracias a @ user2357112. TIL que Python trata a los exponentes sucesivos como una torre de energía.

GolfScript ( 12 7 caracteres)

9,{\?}*

Esto calcula e imprime 8 ^ 7 ^ 6 ^ 5 ^ 4 ^ 3 ^ 2 ~ = 10 ^ 10 ^ 10 ^ 10 ^ 183230. Para imprimirlo (no importa el cálculo) en 10 ^ 1000 años ~ = 10 ^ 1007.5 segundos, necesita imprimir aproximadamente 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 es un lenguaje de 8 bits con valores solo representados por canicas en una máquina similar a Rube Goldberg, por lo que esto no fue muy fácil. Este enfoque es más o menos equivalente al siguiente pseudocódigo:

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

dado que el valor máximo es 256, (representado por 0 en el programa Marbleous, que se maneja de manera diferente en diferentes lugares) recursiveFunction (1) se llamará un total de lo 256!*512^256cual es igual 10^1200, lo suficientemente fácil como para sobrevivir al universo.

Marbelous no tiene un intérprete muy rápido, parece que puede ejecutar 10^11llamadas de esta función por año, lo que significa que estamos viendo un tiempo de ejecución de 10^1189años.

Explicación adicional de la placa Marbelous

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

00es un lenguaje literal (o canica), representado en hexadecimal (por lo tanto, 0). Esta canica cae sobre el --, que disminuye cualquier canica en 1 (00 se envuelve y se convierte en FF o 255 en decimal). El mármol con ahora el valor FF cae sobre el \\que lo empuja una columna a la derecha, hacia abajo @0. Este es un portal y teletransporta la canica al otro @0dispositivo. Allí, la canica aterriza en el /\dispositivo, que es un duplicador, coloca una copia de la canica --a su izquierda (esta canica seguirá girando entre los portales y se reducirá en cada bucle) y una a la =0derecha.=0compara la canica con el valor cero y deja que la canica caiga si es igual y la empuja hacia la derecha si no es así. Si la canica tiene el valor 0, aterriza en &0un sincronizador, que explicaré más adelante, más adelante.

Con todo, esto solo comienza con una canica de valor 0 en un bucle y lo disminuye hasta que llegue a 0 nuevamente, luego coloca esta canica de valor 0 en un sincronizador y sigue haciendo bucles al mismo tiempo.

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

}0es un dispositivo de entrada, inicialmente la enésima entrada de línea de comando (base 0) cuando se llama al programa se coloca en cada }ndispositivo. Entonces, si llama a este programa con la entrada de línea de comando 2, una canica de valor 02 reemplazará esto }0. Luego, esta canica cae en el &0dispositivo, otro sincronizador, los &nsincronizadores retienen canicas hasta que &nse archivan todos los demás correspondientes . Luego, la canica se disminuye, se teletransporta y se duplica como en el bucle explicado anteriormente. Luego, se verifica la desigualdad con cero ( >0) en la copia correcta si no es 0, se cae. Si es 0, se empuja hacia la derecha y aterriza !!, lo que termina el tablero.

Bien, hasta ahora tenemos un ciclo que cuenta regresivamente de 255 a 0 y permite que otro ciclo similar (alimentado por la entrada de la línea de comando) se ejecute una vez cada vez que llega a 0. Cuando este segundo ciclo se ha ejecutado n veces (máximo 256 ) el programa termina. Entonces eso es un máximo de 65536 carreras del bucle. No lo suficiente como para sobrevivir al universo.

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

Esto debería comenzar a parecer familiar, la entrada se disminuye una vez, luego este valor se repite y se copia (tenga en cuenta que la canica solo se disminuye una vez, no en cada ejecución del bucle). Luego se verifica la igualdad a 0 y si no es cero, aterriza MB. Esta es una función en Marbelous, cada archivo puede contener varias placas y cada placa es una función, cada función debe nombrarse precediendo la cuadrícula por :[name]. Todas las funciones, excepto la primera función del archivo, que tiene un nombre estándar: MB. Entonces, este ciclo llama continuamente a la placa principal nuevamente con un valor de n - 1donde n es el valor con el que se llamó a esta instancia de la función.

¿Entonces por qué n*512?

Bueno, el primer ciclo se ejecuta en 4 ticks (y 256 veces) y el segundo ciclo se ejecuta n veces antes de que finalice el tablero. Esto significa que el tablero se ejecuta durante aproximadamente n*4*256ticks. El último bucle (que llama a la función recursiva) es compacto y se ejecuta en 2 tics, lo que significa que logra llamar a los n*4*256/2 = n*512tiempos de la función .

¿Cuáles son los símbolos que no mencionaste?

\/ es un contenedor de basura, que elimina las canicas del tablero, esto asegura que las canicas descartadas no interfieran con otras canicas que están dando vueltas y evitan que el programa finalice.

Prima

Dado que las canicas que caen del fondo de una placa maravillosa salen a STDOUT, este programa imprime una gran cantidad de caracteres ASCII mientras se ejecuta.

Perl, 66 58 caracteres

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

Lo anterior es una implementación de la función Ackermann – Péter . No tengo idea de cuán grande es A (9,9), pero estoy bastante seguro de que tomará un tiempo sorprendentemente largo evaluarlo.

MATLAB, 58 52 caracteres

Necesitamos al menos una solución aritmética de precisión finita, por lo tanto:

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

x = unos (1,999); y = x; mientras que cualquiera (y), y = mod (y + x, primos (7910)); final

( con agradecimiento a @DennisJaheruddin por eliminar 6 caracteres )

El número de ciclos necesarios para completar viene dado por el producto de los primeros 999 primos. Dado que la gran mayoría de estos son más de 10, el tiempo necesario para lograr la convergencia sería cientos o miles de órdenes de magnitud mayores que el límite de tiempo mínimo.

Mathematica, 25 19 bytes

Esta solución fue publicada antes de que las funciones de tiempo fueran descalificadas.

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

TimeUsed[]devuelve los segundos desde que comenzó la sesión, y Mathematica usa tipos de precisión arbitraria. Hay unos 10 ⁷ segundos en un año, por lo que esperar 10 ¹⁰⁰⁰⁰ segundos debería ser suficiente.

Alternativa más corta / más simple (/ válida):

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

Vamos a contar en su lugar. Tendremos que contar un poco más, porque podemos hacer muchos incrementos en un segundo, pero el límite más alto en realidad no cuesta caracteres.

Técnicamente, en ambas soluciones, podría usar un límite mucho más bajo porque el problema no especifica una velocidad mínima del procesador.

Python 3 - 49

Esto hace algo útil: calcula Pi con una precisión sin precedentes utilizando la serie infinita Gregory-Leibniz.

En caso de que te lo estés preguntando, este programa recorre muchas 10**10**10**2.004302604952323veces.

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

Precisión arbitraria: 78

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

Fuente de imagen

El aliento terminal

Debido a los enormes cálculos que tienen lugar, las 1e99**1e99iteraciones tardan menos de 1e99**1e99años. Ahora, (1e99**1e99)-1e1000casi no hay diferencia. Eso significa que este programa durará mucho más que la muerte de nuestro universo.

Renacimiento

Ahora, los científicos proponen que en 10**10**56 years, el universo renacerá debido a fluctuaciones cuánticas o túneles. Entonces, si cada universo es exactamente el mismo, ¿cuántos universo vivirá mi programa?

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

Suponiendo que el universo siempre vivirá 1e10+1e1000años y luego tardará 10**10**56años en reiniciarse, mi programa vivirá a través de 1e9701universos. Esto supone, por supuesto, que unobtainium puede vivir a través del Big Bang.

Python 59 (funciona la mayor parte del tiempo)

No pude resistir

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

Si bien es cierto que esto podría terminar teóricamente en menos de un milisegundo, el tiempo de ejecución promedio supera con creces 10^400la vida útil especificada del universo. Gracias a @BetaDecay, @undergroundmonorail y @DaboRoss por obtener 17 caracteres más o menos.

J - 5 caracteres, creo

Tenga en cuenta que todo lo siguiente está en aritmética de precisión arbitraria, porque el número 9 siempre tiene un poco xal lado.

En siete caracteres, tenemos !^:!!9x, que es como correr

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

en aritmética de precisión arbitraria. Esto definitivamente está por encima del límite porque Synthetica lo dijo , así que tenemos un límite superior.

En seis caracteres, también podemos escribir ^/i.9x, que calcula cada resultado intermedio de 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8. Wolfram | Alpha dice que 2^3^4^5^6^7^8es aproximadamente 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 6.65185, lo que probablemente también despeja la inspección.

También tenemos el cinco por carbón !!!9x, que es justo ((9!)!) !. W | A dice que es 10 ^ 10 ^ 10 ^ 6.2695, que aún debería ser lo suficientemente grande ... Eso es como 1.6097e1859933dígitos, que es decididamente mayor que 3.154e1016la cantidad de nanosegundos en el universo, pero admito que no tengo idea de cómo uno podría descubrir los verdaderos tiempos de ejecución de estas cosas.

Sin embargo, la impresión solo debería tomar el tiempo suficiente para durar más que el universo, por lo que debería estar bien.

C, 63 56 caracteres

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

Esto se basa en una idea de un tipo llamado Wilhelm. Mi única contribución es condensar el código en esta pieza corta (e ilegible).

Probar que termina se hace por inducción.

• Si x es 0, termina inmediatamente.
• Si termina para x-1 y cualquier y, también termina para x, esto se puede mostrar por inducción.

Prueba de la inducción paso a paso por inducción:

• Si y es 0, solo hay una llamada recursiva con x-1, que termina por suposición de inducción.
• Si f (x, y-1) termina, entonces f (x, y) también termina porque la llamada más interna de f es exactamente f (x, y-1) y la llamada más externa termina de acuerdo con la síntesis de inducción.

El tiempo de ejecución esperado es A (9,9) / 11837 segundos. Este número tiene más dígitos que el número de quarks en el universo observable.

Matlab ( 10 8 caracteres)

1:9e1016

En mi humilde opinión, la mayoría de las entradas se esfuerzan demasiado al calcular cosas grandes y complicadas. Este código simplemente inicializará una matriz de 9x10 ¹⁰¹⁶ double s contando desde 1, que toma 7.2x10 ^ ¹⁰¹⁷ bytes. En una CPU moderna, con un ancho de banda de memoria máxima de 21 GB / s o 6.63x10 ^ ¹⁷ bytes / año , se tardará al menos 1.09x10 ¹⁰⁰⁰ años, incluso inicializar la matriz, y mucho menos tratar de imprimirlo ya no me molesté suprimiendo la salida con un punto y coma final. (;

soluciones antiguas

nan(3e508)

Alternativamente

inf(3e508)

Este código simplemente creará una matriz cuadrada de NaNs / infinitos de tamaño 3e508x 3e508 = 9e1016dobles o 7.2e1017bytes de 8 bytes.

Perl, 16 caracteres

/$_^/for'.*'x1e9

Esto crea una cadena que repite ". *" Mil millones de veces, luego la usa como aguja y como pajar en una combinación de expresiones regulares. Esto, a su vez, hace que el motor de expresiones regulares intente todas las particiones posibles de una cadena de dos mil millones de caracteres. De acuerdo con esta fórmula de Wikipedia , hay aproximadamente 10 ^{35218 de} tales particiones.

La solución anterior tiene 16 caracteres de longitud, pero solo requiere aproximadamente 2 Gb de memoria, lo que significa que se puede ejecutar en una computadora real. Si asumimos una memoria infinita y un tamaño de registro finito (lo que probablemente no tiene sentido), se puede acortar a 15 caracteres y aumentar drásticamente el tiempo de ejecución:

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

(No lo he probado, pero creo que podría funcionar con un Perl de 32 bits construido en una máquina de 64 bits con al menos 6 Gb de RAM).

Notas:

• x es el operador de repetición de cadena.
• el forno es un bucle real; solo se usa para guardar un personaje (en comparación con $_=".*"x1e9;/$_^/).
• el final ^en la expresión regular asegura que solo la cadena vacía puede coincidir; Como los cuantificadores de expresiones regulares son codiciosos por defecto, esto es lo último que intentará el motor.
• Los valores de referencia en mi computadora para los valores (1..13) sugieren que el tiempo de ejecución es en realidad O (exp (n)), que es incluso más que el O (exp (sqrt (n))) en la fórmula de Wikipedia.

J (12)

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

A qué se reduce esto en Python (suponiendo que !funcione):

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

EDITAR:

Bueno, el programa puede tomar, como máximo, 2 × 10^-1858926segundos por ciclo, para completar dentro del tiempo requerido. Consejo: esto ni siquiera funcionará para el primer ciclo, no importa el último;).

Además: este programa podría necesitar más memoria de la que hay entropía en el universo ...

C # 217

No soy muy golfista, pero no pude resistir la función de Ackerman . Tampoco sé cómo calcular el tiempo de ejecución, pero definitivamente se detendrá, y definitivamente durará más que esta versión .

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));}
}

Primer intento de código de golf pero aquí va.

VBA - 57 45

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

Entonces X aumentará en uno si ocurre un evento 1 en 2 ^ 128 y se restablecerá si no ocurre. El código termina cuando este evento ocurre 2 ^ 64 + 1 veces seguidas. No sé cómo comenzar a calcular el tiempo, pero supongo que es enorme.

EDITAR: Calculé las matemáticas y la probabilidad de que esto suceda en cada ciclo es 1 en 2 ^ 128 ^ (1 + 2 ^ 64), que tiene aproximadamente 20000 dígitos de largo. Suponiendo que 1000000 bucles / seg (número de bolas de la nada) y 30000000 s / año que son 3 * 10 ^ 13 ciclos por año tiempo 10 ^ 1000 años restantes son 3 * 10 ^ 1013 ciclos, por lo que esto probablemente duraría alrededor de 20 veces el tiempo restante en el universo. Me alegra que mis matemáticas respalden mi intuición.

C, 30 caracteres

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

Suponiendo que el complemento de dos se haya desbordado firmado y las entradas de 32 bits, esto se ejecutará durante aproximadamente 2 ^{2 32} llamadas de función, lo que debería ser suficiente tiempo para que el universo finalice.

GolfScript, 13 caracteres

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

Este programa solo cuenta de 0 a 10 ^{9 9 −1} = 10 ^387420488 . Suponiendo, de manera optimista, que la computadora funciona a 100 GHz y puede ejecutar cada iteración del programa en un solo ciclo, el programa se ejecutará durante 10 ^{9 9 −12} segundos, o aproximadamente 3 × 10 ^{9 9 −20} = 3 × 10 ^387420469 años.

Para probar el programa, puede reemplazarlo 9con a 2, lo que hará que se detenga en 10 ^{2 2 −1} = 10 ³ = 1000. (Si usa un en 3lugar de a, 2hará que se detenga en 10 ^{3 3 −1} = 10 ²⁶ , que , incluso con los supuestos optimistas anteriores, no alcanzará al menos unos pocos millones de años).

Autohotkey 37

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

Haskell, 23

main=interact$take$2^30

Este programa termina después de leer 1073741824 caracteres de stdin. Si se ejecuta sin canalizar ningún dato astdin , deberá escribir este número de caracteres en su teclado. Suponiendo que su teclado tiene 105 teclas, cada una clasificada para ciclos mecánicos de 100k y programadas para generar pulsaciones de teclas no muertas, la repetición automática está desactivada y el zócalo del teclado permite 100 ciclos de conexión, esto proporciona el número máximo de pulsaciones de tecla por computadora de 1050000000, que es no es suficiente para que el programa finalice.

Por lo tanto, el programa solo terminará cuando haya un mejor hardware disponible en términos de número de ciclos, lo que efectivamente nunca está en este universo en ejecución. Quizás la próxima vez, cuando la calidad tenga mayor prioridad que la cantidad. Hasta entonces, este programa termina en principio pero no en la práctica.

~ ATH, 56

En el lenguaje ficticio ~ ATH :

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

~ ATH es un lenguaje insufrible para trabajar. Su lógica se compone de nada más que bucles infinitos, o en el mejor de los casos, bucles de construcción efectivamente interminable.

Lo que hacen muchos codificadores de ~ ATH es importar construcciones finitas y unir los bucles a su vida útil. Por ejemplo, el ciclo principal aquí terminará con la muerte del universo, etiquetado como U. De esa manera, solo tendrá que esperar miles de millones de años para que finalice en lugar de para siempre.

Pido disculpas por las violaciones de la brecha límite; Pensé que era demasiado relevante para dejarlo pasar.

Si alguien realmente se divirtió con esto, más detalles: (1) , (2) , (3) , (4)

Rubí (34)

¡La línea ([0]*9).permutation.each{print}tarda aproximadamente 2.47 segundos para 9! imprime en mi máquina, mientras que la línea ([0]*10).permutation.each{print}tarda unos 24.7 segundos por 10! impresiones, así que supongo que puedo extrapolar aquí y calcular (24.7/10!)*470! seconds in yearscuál es 6.87 * 10 ^ 1040, que debería ser el tiempo de ejecución 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)

Esto usa la función Ackermann que se puede escribir 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));
}

Su tiempo de ejecución aumenta exponencialmente y, por lo tanto, toma mucho tiempo calcularlo. Aunque no está en inglés aquí , puede obtener una descripción general de sus valores de retorno. De acuerdo con la tabla ackermann(5,1)es igual a 2↑↑(65533)-3lo que es, ya sabes, muy grande.

Befunge '93 - 40 bytes

(Programa 20x2)

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

Este programa se basa en números aleatorios para retrasarlo. Dado que los intérpretes de Befunge son bastante lentos, este programa debería cumplir con los requisitos. Y si no es así, siempre podemos expandirlo horizontalmente. No estoy exactamente seguro de cómo calcular el tiempo de ejecución esperado de este programa, pero sé que cada uno. tiene una probabilidad de 50/50 de comenzar de nuevo o cambiar su posición horizontal en 1. Hay 18? ¡Creo que debería ser algo similar a (18 ^ 2) !, que según la calculadora de Google es "Infinito"

EDITAR: Vaya, no noté la otra respuesta de Befunge, esta es mi primera publicación aquí. Lo siento.

APL, 10

No creo que esta sea una respuesta válida (ya que no es determinista), pero de todos modos ...

{?⍨1e9}⍣≡1

Este programa calcula una permutación aleatoria de 1e9 números ( ?⍨1e9) y se repite hasta que dos salidas consecutivas sean iguales (⍣≡ )

Entonces, cada vez que se calcula una permutación, ¡tiene 1 en 1000000000! posibilidad de terminar. Y 1000000000! es al menos 10 ^{10 8} .

El tiempo que lleva calcular una permutación se vuelve irrelevante por la masividad de 1000000000 !. Pero algunas pruebas muestran que esto esO(n) y la extrapolación da unos 30 segundos.

Sin embargo, mi intérprete se niega a tomar entradas a la función aleatoria mayor que 2 ³¹ -1 (por lo que usé 1e9), y la generación de permutaciones de números 1000000000 dio un error total en el espacio de trabajo. Sin embargo, conceptualmente se puede hacer con un intérprete APL ideal con memoria infinita.

Esto nos lleva a la posibilidad de usar 2 ⁶³ -1 en lugar de 1e9 para aumentar el tiempo de ejecución hasta al menos 10 ^{10 20} , suponiendo una arquitectura de 64 bits.

Pero espera, ¿es relevante la arquitectura en un intérprete ideal? ¡Demonios, no, así que en realidad no hay límite superior en el tiempo de ejecución!

R, 45 bytes

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

Es un hilo viejo pero no veo respuesta R, ¡y no podemos estar teniendo eso!

El tiempo de ejecución para mí fue de aproximadamente 1s cuando x era 20, lo que sugiere un tiempo de ejecución de 2 ^ 9979 segundos.

Si reemplaza el cero con uno, la salida sería 2 ^ x, pero tal como está la salida es cero, sea lo que sea x (evita problemas de desbordamiento).

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)

Se puede hacer con una memoria mínima (probablemente menos de medio megabyte) pero tarda (probablemente) unos 10 ^8,750 años en detenerse.

Incrementa repetidamente un Little-endian base-9 BigInteger hasta que alcanza 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)

Primero, f es una función factorial recursiva y ultra lenta. Luego, hay 9 * 10⁹⁹⁹ alimentado consigo mismo, lo que genera un OverflowError, pero esto no sucede en esta computadora Unobtanium. ¡For-Loop itera 9E999! ^ (9E999 ^ 9E999)! veces y solo pasa a la siguiente iteración, si 9E999! +1 entradas aleatorias entre 0 y 9E99 * ^ i! son todos 0 y en cada iteración de while-loop s se establece en (9E999 ^ s) !. Olvidé que la impresión de s lleva muuuuccchhhh tiempo ...
Sé que no es la solución más corta, pero creo que es realmente efectiva. ¿Alguien puede ayudarme a calcular el tiempo de ejecución?

Máquina de Turing pero mucho peor , 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

Pruébalo en línea!

Debe ejecutar el Busy Beaver de 6 estados y 2 símbolos desde la página de Wikipedia .

$7.412 \times 10^{36534}$