Escriba el programa más corto posible (longitud medida en bytes) que cumpla los siguientes requisitos:
- sin entrada
- la salida es stdout
- la ejecución finalmente termina
- El número total de bytes de salida excede el número de Graham
Suponga que los programas se ejecutan hasta la terminación "normal" en una computadora ideal 1 capaz de acceder a recursos ilimitados, y que los lenguajes de programación comunes se modifican si es necesario (sin cambiar la sintaxis) para permitir esto. Debido a estos supuestos, podríamos llamar a esto una especie de experimento de Gedanke.
Para comenzar, aquí hay un programa Ruby de 73 bytes que calcula f ω + 1 (99) en la jerarquía de rápido crecimiento :
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
1 EDITAR: más precisamente, supongamos que estamos tomando un sistema existente y lo modificamos solo para que no tenga un límite superior en el tamaño de almacenamiento (pero siempre es finito). No se supone que los tiempos de ejecución de las instrucciones se modifiquen, pero se supone que la máquina es ideal ya que no tendrá un límite superior en su vida útil operativa.
Respuestas:
GolfScript (
4947 caracteres)Vea Lifetime of a worm para muchas explicaciones. En resumen, esto imprime un número mayor que f ω ω (2).
fuente
Haskell
59575563Cómo funciona:
%
simplemente toma una función y la componen-1
veces encimas
; es decir,%3
toma una funciónf
y devuelve una funciónn
que equivale a aplicarlaf
a 3,n-1
veces seguidas. Si iteramos la aplicación de esta función de orden superior, obtenemos una secuencia de funciones de rápido crecimiento, comenzando con la exponenciación, es exactamente la secuencia de tamaños de bosque 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
y así sucesivamente.
((%3)%(3^))n 3
es decir3 ↑ⁿ 3
, lo que aparece en el cálculo del número de Graham. Todo lo que queda por hacer es componer la función(\n -> 3 ↑ⁿ 3) ≡ flip((%3)%(3^))3
más de 64 veces, encima de 4 (el número de flechas con las que comienza el cálculo), para obtener un número mayor que el número de Graham. Es obvio que el logaritmo (¡qué función tan lenta!)g₆₅
Es aún mayor queg₆₄=G
, por lo que si imprimimos ese número, la longitud de salida excedeG
.⬛
fuente
print$((flip((%3)%(3*))3)%2)1
, hay un error en tiempo de ejecución - se puede decir que por qué? Tiene éxito cuando2
se cambia a1
(la salida es 81).Int
rápidamente. En un sistema de 64 bits, eso consume demasiada memoria para reproducirse, pero, por supuesto, aún no permite alcanzarloG
. Necesito el tipo (big-int)Integer
, por lo que no puedo usar!!
; espera ...%
.((%3)%(3*))2 n
realidad crece más rápido de lo que dices (algo bueno ), pero mi Haskell-fu es inadecuado para entender por qué. Porquen = 0, 1, 2, ...
, en lugar de dar3, 3^3, 3^(3^3), ...
, da3, 3^(3+1), 3^((3^(3+1))+1), ...
.((%3)%(3*))n 3
es más grande que3 ↑ⁿ 3
". ¿O quieres decir algo más? De todos modos, cambié la definición para que sean todas las igualdades (al menos eso creo, demasiado flojo para comprobar ahora ...) en lugar de grandes gracias. Y si cambias66
a65
, en realidad se produceG
, ¿no es agradable?Pyth ,
2928 bytesDefine un lambda para hiperoperación y lo llama de forma recursiva. Como la definición del número de Graham, pero con valores más grandes.
Esta:
Define una lambda, aproximadamente igual a la pitón
Esto proporciona la función de hiperoperación, g (G, H) = 3 ↑ G + 1 (H + 1).
Entonces, por ejemplo, g (1,2) = 3 ↑ 2 3 = 7,625,597,484,987, que puedes probar aquí .
V<x><y>
comienza un ciclo que ejecuta el cuerpo,y
,x
veces.=gZT
es el cuerpo del bucle aquí, que es equivalente aZ=g(Z,10)
El código:
Debería llamar recursivamente a la hiperoperación más de 64 veces, dando el número de Graham.
En mi respuesta, sin embargo, he reemplazado los dígitos individuales con
T
, que se inicializa a 10, y aumentó la profundidad de recursión a 99. Usando la notación de matriz de Graham, el número de Graham es [3,3,4,64], y mi el programa genera el mayor [10,11,11,99]. También eliminé el)
que cierra el ciclo para guardar un byte, por lo que imprime cada valor sucesivo en las 99 iteraciones.fuente
Python (111 + n), n = longitud (x)
Aunque este no es tan corto como el programa Ruby del respondedor, lo publicaré de todos modos, para descartar esta posibilidad.
Utiliza la función de Ackermann y llama a la función de Ackermann, siendo myn los valores de otra llamada a la función de Ackermann, y se repite 1000 veces.
Esto es probablemente más grande que el número de Graham, pero no estoy seguro, porque nadie sabe la longitud exacta de la misma. Se puede extender fácilmente, si no es más grande.
fuente
return
declaración o unlambda
.exec'x=A(x,x);'*x;print x
, entonces el programa está bien y el resultado es aproximadamente f_ (ω + 1) (x) (suponiendo que el código de función de Ackermann sea correcto), que tiene más de G bytes incluso para x = 99, digamos . (En mi programa Ruby,f[m,n]
es una versión deA(m,n)
.)eval
lugar deexec
, su última línea podría serf=lambda x:A(x,x);print eval('f('*x+'x'+')'*x)
. Además, su definición de A (m, n) debe corregirse según el comentario de la cabina.Ruby,
545250 bytesRuby,
858176716864635957 bytesJerarquía de crecimiento bastante rápido con f (a + 1)> f ω + 1 (a).
Ruby, 61 bytes
Básicamente una función de Ackermann con un giro.
Ruby,
6359 bytesOtro rubí,
7471 bytesBásicamente, Ackermann funciona para sí mismo 99 veces.
fuente
Python: 85
Que tal vez podría acortarse a 74 +
length(X)
:Dónde
X
hay un número grande apropiado tal que la hiperoperación resultante3, 3
sea mayor que el número de Graham (si este número es menor que99999999999
entonces se guarda algún byte).Nota: supongo que el código de Python se ejecuta en el intérprete interactivo, por lo tanto, el resultado se imprime en stdout; de lo contrario, agregue
9
bytes a cada solución para la llamada aprint
.fuente
Javascript, 83 bytes
Otra solución de la función de Ackermann.
fuente
JavaScript, 68 bytes, sin embargo, sin competencia para usar ES6
a
La función es similar a la notación de flecha hacia arriba con la base 9.b
la función es: b (x) = b x (9).b(99)
es ~ f ω + 1 (99), en comparación con el número de Graham <f ω + 1 (64).fuente