Programa de terminación más corto cuyo tamaño de salida excede el número de Graham

37

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.

res
fuente
¡Esto lleva mi pregunta de tetración a un nivel completamente nuevo!
MrZander
1
Hubo una vez un concurso de programación similar llamado Bignum Bakeoff. Algunas de las entradas son bastante interesantes; los resultados están aquí: djm.cc/bignum-results.txt
Danny Chia

Respuestas:

11

GolfScript ( 49 47 caracteres)

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

Vea Lifetime of a worm para muchas explicaciones. En resumen, esto imprime un número mayor que f ω ω (2).

Peter Taylor
fuente
f_ (ω ^ ω) (2) es casi tan grande como g_ (f_8 (8)), por lo que no es tan exagerado como implicaría esa expresión.
Simply Beautiful Art
21

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

Cómo funciona: %simplemente toma una función y la compone n-1veces encima s; es decir, %3toma una función fy devuelve una función nque equivale a aplicarla fa 3, n-1veces 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 3es decir 3 ↑ⁿ 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^))3má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 que g₆₄=G, por lo que si imprimimos ese número, la longitud de salida excede G.

dejó de girar en sentido antihorario
fuente
Cuando probar esto con print$((flip((%3)%(3*))3)%2)1, hay un error en tiempo de ejecución - se puede decir que por qué? Tiene éxito cuando 2se cambia a 1(la salida es 81).
res
Oh ... ideone parece ejecutar una versión de 32 bits, por lo que se desborda Intrápidamente. En un sistema de 64 bits, eso consume demasiada memoria para reproducirse, pero, por supuesto, aún no permite alcanzarlo G. Necesito el tipo (big-int) Integer, por lo que no puedo usar !!; espera ...
dejó de girar en sentido contrario a las agujas del reloj el
Lo arregló ahora, tenía que usar la recursividad explícita para implementar %.
dejó de girar en sentido antihorario
Creo que en ((%3)%(3*))2 nrealidad crece más rápido de lo que dices (algo bueno ), pero mi Haskell-fu es inadecuado para entender por qué. Porque n = 0, 1, 2, ..., en lugar de dar 3, 3^3, 3^(3^3), ..., da 3, 3^(3+1), 3^((3^(3+1))+1), ....
res
Como dije: " ((%3)%(3*))n 3es más grande que 3 ↑ⁿ 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 cambias 66a 65, en realidad se produce G, ¿no es agradable?
dejó de girar en sentido antihorario el
5

Pyth , 29 28 bytes

M?*GHgtGtgGtH^ThH=ZTV99=gZTZ

Define 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:

M?*GHgtGtgGtH^3hH

Define una lambda, aproximadamente igual a la pitón

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

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 , xveces.
=gZTes el cuerpo del bucle aquí, que es equivalente aZ=g(Z,10)

El código:

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

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.

KSmarts
fuente
3

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.

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))
beary605
fuente
salida a stdout? Además, necesita una returndeclaración o un lambda.
stand
77
Además, si A (m, n) devuelve un solo valor, ¿no le falta a A (A (5,5)) un argumento? ... Este es el problema con un desafío como este: alienta a las personas a no probar su código, porque una ejecución completa es puramente teórica.
breadbox
Si reemplaza su última línea con 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 de A(m,n).)
res
@breadbox - Buen punto ... Las preguntas teóricas como esta requieren que nos aseguremos de que un programa esté bien para casos de prueba de parámetros pequeños (es decir, no teóricos) que se generalicen claramente para dar una respuesta correcta.
res
1
Es más largo, pero si quieres usarlo en evallugar deexec , su última línea podría ser f=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.
res
2

Ruby, 54 52 50 bytes

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

Ruby, 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]

Jerarquía de crecimiento bastante rápido con 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]

Básicamente una función de Ackermann con un giro.


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

Otro rubí, 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

Básicamente, Ackermann funciona para sí mismo 99 veces.

Simplemente hermoso arte
fuente
0

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 tal vez podría acortarse a 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)

Dónde X hay un número grande apropiado tal que la hiperoperación resultante 3, 3sea ​​mayor que el número de Graham (si este número es menor que 99999999999entonces 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 9bytes a cada solución para la llamada aprint .

Bakuriu
fuente
2
Su solución de 74 bytes no produce una salida lo suficientemente grande.
lirtosiast
0

Javascript, 83 bytes

Otra solución de la función de 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)
SuperJedi224
fuente
0

JavaScript, 68 bytes, sin embargo, sin competencia para usar 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 La función es similar a la notación de flecha hacia arriba con la 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

bla 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).

Naruyoko
fuente
Si ha marcado esta no competencia debido a que el idioma es más nuevo que la pregunta, ya no tiene que hacer eso
Jo King