Reinicio de BigNum Bakeoff

12

Algunos de ustedes pueden estar familiarizados con el BigNum Bakeoff , que terminó de manera bastante interesante. El objetivo puede resumirse más o menos como escribir un programa en C cuya producción sería la más grande, bajo algunas restricciones y condiciones teóricas, por ejemplo, una computadora que podría ejecutar el programa.

En el mismo espíritu, estoy planteando un desafío similar abierto a todos los idiomas. Las condiciones son:

  • Máximo 512 bytes .

  • El resultado final debe imprimirse en STDOUT. Este es tu puntaje. Si se imprimen varios enteros, se concatenarán.

  • La salida debe ser un número entero. (Nota: Infinity no es un número entero ).

  • No hay constantes incorporadas mayores de 10, pero los números / dígitos están bien (por ejemplo, la constante de Avogadro (como una constante incorporada) no es válida, pero 10000 no lo es).

  • El programa debe finalizar cuando se proporcionan recursos suficientes para ejecutarse.

  • La salida impresa debe ser determinista cuando se proporcionan recursos suficientes para ejecutarse.

  • Se le proporcionan enteros o bigints suficientemente grandes para que su programa se ejecute. Por ejemplo, si su programa requiere la aplicación de operaciones básicas a números menores de 10 1,000,000 , entonces puede suponer que la computadora que ejecuta esto puede manejar números de al menos hasta 10 1,000,000 . (Nota: Su programa también puede ejecutarse en una computadora que maneja números de hasta 10 2,000,000 , por lo que simplemente llamar al número entero máximo que la computadora puede manejar no dará resultados deterministas).

  • Se le proporciona suficiente potencia informática para que su programa termine de ejecutarse en menos de 5 segundos. (Por lo tanto, no se preocupe si su programa ha estado ejecutándose durante una hora en su computadora y no va a terminar pronto).

  • Sin recursos externos, así que no piense en importar esa función de Ackermann a menos que sea una función integrada.

Todos los artículos mágicos están siendo prestados temporalmente de una deidad generosa.

Extremadamente grande con límite desconocido.

donde B³F es el ordinal Iglesia-Kleene con la secuencia fundamental de

B³F[n] = B³F(n), the Busy Beaver BrainF*** variant
B³F[x] = x, ω ≤ x < B³F

Tabla de clasificación:

  1. Simply Beautiful Art , Ruby f ψ 0 (X (Ω M + X (Ω M + 1 Ω M + 1 ) )) + 29 (9 9 9 )

  2. Steven H , Pyth f ψ (Ω Ω ) + ω² + 183 (256 27! )

  3. Leaky Nun , Python 3 f ε 0 (9 9 9 )

  4. fejfo , Python 3 f ω ω 6 (f ω ω 5 (9e999))

  5. Steven H , Python 3 f ω ω + ω² (9 9 9 99 )

  6. Simply Beautiful Art , Ruby f ω + 35 (9 9 99 )

  7. i .. , Python 2 , f 3 (f 3 (141))

Algunas notas al margen:

Si no podemos verificar su puntaje, no podemos ponerlo en la tabla de clasificación. Por lo tanto, puede esperar explicar un poco su programa.

Del mismo modo, si no comprende qué tan grande es su número, explique su programa e intentaremos resolverlo.

Si utiliza un tipo de programa de número de Loader , lo ubicaré en una categoría separada llamada "Extremadamente grande con límite desconocido" , ya que el número de Loader no tiene un límite superior no trivial en términos de la jerarquía de rápido crecimiento para ' secuencias fundamentales estándar.

Los números se clasificarán a través de la jerarquía de rápido crecimiento .

Para aquellos que deseen aprender cómo usar la jerarquía de rápido crecimiento para aproximar números realmente grandes, estoy alojando un servidor Discord solo para eso. También hay una sala de chat: Ordinality .

Desafíos similares:

Número más grande imprimible

Golf un número más grande que el ÁRBOL (3)

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

Para aquellos que desean ver algunos programas simples que generan la jerarquía de rápido crecimiento para valores pequeños, aquí están:

Ruby: jerarquía de rápido crecimiento

#f_0:
f=->n{n+=1}

#f_1:
f=->n{n.times{n+=1};n}

#f_2:
f=->n{n.times{n.times{n+=1}};n}

#f_3:
f=->n{n.times{n.times{n.times{n+=1}}};n}

#f_ω:
f=->n{eval("n.times{"*n+"n+=1"+"}"*n);n}

#f_(ω+1):
f=->n{n.times{eval("n.times{"*n+"n+=1"+"}"*n)};n}

#f_(ω+2):
f=->n{n.times{n.times{eval("n.times{"*n+"n+=1"+"}"*n)}};n}

#f_(ω+3):
f=->n{n.times{n.times{n.times{eval("n.times{"*n+"n+=1"+"}"*n)}}};n}

#f_(ω∙2) = f_(ω+ω):
f=->n{eval("n.times{"*n+"eval(\"n.times{\"*n+\"n+=1\"+\"}\"*n)"+"}"*n);n}

etc.

Para ir de f_xa f_(x+1), agregamos un bucle de n.times{...}.

De lo contrario, estamos diagonalizando contra todos los anteriores, por ejemplo

f_ω(1) = f_1(1)
f_ω(2) = f_2(2)
f_ω(3) = f_3(3)

f_(ω+ω)(1) = f_(ω+1)(1)
f_(ω+ω)(2) = f_(ω+2)(2)
f_(ω+ω)(3) = f_(ω+3)(3)

etc.

Simplemente hermoso arte
fuente
¿Los números cuentan como constantes incorporadas?
PyRulez
3
@CloseVoters ¿Cómo puede ser esto demasiado amplio? Bueno, pedirle al usuario que muestre un número en infinitos números no es lo mismo que pedirle al usuario que elija una de las infinitas tareas que hacer. Para ser justos, esta pregunta pide al usuario que haga lo mismo también. 4 votos cerrados ya son demasiado amplios ...
user202729
1
@ Οurous Sí, puede suponer eso. Pero tenga en cuenta que cuando su programa recibe más recursos, incluido un cálculo más rápido, la salida aún debe ser determinista.
Simplemente hermoso arte
1
Dije en la otra sección de comentarios por qué creo que la función limitada Brainfuck Busy Beaver será exponencial, pero me gustaría agregar que, en general, no creo que el ordinal de Church-Kleene sea el nivel apropiado para cualquier programa de computadora . Una función que se puede codificar con un programa es computable y, por lo tanto, debe caer en las funciones probadamente recursivas de una teoría del sonido recursivo suficientemente fuerte. Esa teoría tendrá un ordinal teórico de prueba recursiva, y esa función estará por debajo de ese ordinal en el FGH, suponiendo secuencias fundamentales razonables.
Deedlit
1
Por supuesto, la función Busy Beaver real no puede codificarse en el programa (aparte de los lenguajes hipercomputacionales), y las funciones restringidas de Busy Beaver que pueden programarse deben necesariamente ser mucho más lentas.
Deedlit

Respuestas:

7

Rubí, f ψ 0 (X (Ω M + X (Ω M + 1 Ω M + 1 ) )) + 29 (9 9 9 )

donde M es el primer 'ordinal' de Mahlo, X es la función chi (función de colapso de Mahlo) y ψ es la función de colapso ordinal.

f=->a,n,b=a,q=n{c,d,e=a;!c ?[q]:a==c ?a-1:e==0||e&&d==0?c:e ?[[c,d,f[e,n,b,q]],f[d,n,b,q],c]:n<1?9:!d ?[f[b,n-1],c]:c==0?n:[t=[f[c,n],d],n,c==-1?[]:d==0?n:[f[d,n,b,t]]]};(x=9**9**9).times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{h=[];x.times{h=[h,h,h]};h=[[-1,1,[h]]];h=f[h,p x*=x]until h!=0}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}

Pruébalo en línea!

Desglose de código:

f=->a,n,b=a,q=n{          # Declare function
                c,d,e=a;          # If a is an integer, c=a and d,e=nil. If a is an array, a=[c,d,e].compact, and c,d,e will become nil if there aren't enough elements in a (e.g. a=[1] #=> c=1,d=e=nil).
                        !c ?[q]:          # If c is nil, return [q], else
                                a==c ?a-1:          # If a==c, return a-1, else
                                          e==0||e&&d==0?c:          # If e==0 or e is not nil and d==0, return c, else
                                                          e ?[[c,d,f[e,n,b,q]],f[d,n,b,q],c]:          # If e is not nil, return an array inside an array, else
                                                                                             n<1?9:          # If n<1, return 9, else
                                                                                                   !d ?[f[b,n-1],c]:          # If d is nil, return [f[b,n-1],c], else
                                                                                                                    c==0?n:          # If c==0, return n, else
                                                                                                                           [t=[f[c,n],d],n,c==-1?[]:d==0?n:[f[d,n,b,t]]]          # t=[f[c,n],d]. If c==-1, return [t,n,[]], else if d==0, return [t,n,n], else return [t,n,[f[d,n,b,t]]].
                                                                                                                                                                        };          # End of function
                                                                                                                                                                          (x=9**9**9)          # Declare x
                                                                                                                                                                                     x.times{...}          # Looped within 33 x.times{...} loops
                                                                                                                                                                                                 h=[];          # Declare h
                                                                                                                                                                                                      x.times{h=[h,h,h]};          # Nest h=[h,h,h] x times
                                                                                                                                                                                                                         h=f[h,p x*=x]          # Apply x*=x, print x, then h=f[h,x]
                                                                                                                                                                                                                                      until h==0          # Repeat previous line until h==0

Desglose matemático:

freduce abasado en n,b,q.

La idea básica es tener un anidado extremadamente ay reducirlo repetidamente hasta que se reduzca a a=0. Por simplicidad, dejemos

g[0,n]=n
g[a,n]=g[f[a,n],n+1]

Por ahora, solo preocupémonos n.

Para cualquier número entero k, obtenemos f[k,n]=k-1, así podemos ver que

g[k,n]=n+k

Tenemos entonces que, para cualquier d, f[[0,d],n]=npara que podamos ver que

g[[0,d],n]
= g[f[[0,d],n],n+1]
= g[n,n+1]
= n+n+1

Tenemos entonces que, para cualquier c,d,e, f[[c,0,e],n]=f[[c,d,0],n]=c. Por ejemplo,

g[[[0,d],0,e],n]
= g[f[[[0,d],0,e]],n+1]
= g[[0,d],n+1]
= (n+1)+(n+1)+1
= 2n+3

Tenemos entonces que, para cualquier c,d,etal que no caiga en el caso anterior, f[[c,d,e],n]=[[c,d,f[e,n]],f[d,n],e]. Aquí es donde comienza a complicarse. Algunos ejemplos:

g[[[0,d],1,1],n]
= g[f[[[0,d],1,1],n],n+1]
= g[[[0,d],1,0],0,[0,d]],n+1]
= g[f[[[0,d],1,0],0,[0,d]],n+1],n+2]
= g[[[0,d],1,0],n+2]
= g[f[[[0,d],1,0],n+2],n+3]
= g[[0,d],n+3]
= (n+3)+(n+3)+1
= 2n+7

#=> Generally g[[[0,d],1,k],n] = 2n+4k+3

g[[[0,d],2,1],n]
= g[f[[[0,d],2,1],n],n+1]
= g[[[[0,d],2,0],1,[0,d]],n+1]
= g[f[[[[0,d],2,0],1,[0,d]],n+1],n+2]
= g[[[[[0,d],2,0],1,n+1],0,[[0,d],2,0]]],n+2]
= g[f[[[[[0,d],2,0],1,n+1],0,[[0,d],2,0]]],n+2],n+3]
= g[[[[0,d],2,0],1,n+1],n+3]
= ...
= g[[[0,d],2,0],3n+6]
= g[f[[[0,d],2,0],2n+6],3n+7]
= g[[0,d],3n+7]
= (3n+7)+(3n+7)+1
= 6n+15

Aumenta rápidamente desde allí. Algunos puntos de interes:

g[[[0,d],3,[0,d]],n] ≈ Ack(n,n), the Ackermann function
g[[[0,d],3,[[0,d],0,0]],63] ≈ Graham's number
g[[[0,d],5,[0,d]],n] ≈ G(2^^n), where 2^^n = n applications of 2^x, and G(x) is the length of the Goodstein sequence starting at x.

Finalmente, la introducción de más argumentos de la ffunción, así como más casos para la matriz, nos permite superar las notaciones computables más nombradas. Algunos particularmente conocidos:

g[[[0],3,[0,d]],n] ≈ tree(n), the weak tree function
g[[[[0],3,[0,d]],2,[0,d]],n] ≈ TREE(n), the more well-known TREE function
g[[[[0,d]],5,[0,d]],n] >≈ SCG(n), sub-cubic graph numbers
g[[[0]],n] ≈ S(n), Chris Bird's S function
Simplemente hermoso arte
fuente
1
Explicación ordinal?
CalculatorFeline
¿Es este su mayor número definido todavía? Parece que sí!
ThePlasmaRailgun
3

Pyth, f ψ (Ω Ω ) + ω 2 +183 (~ 256 27! )

=QC`.pGL&=^QQ?+Ibt]0?htb?eb[Xb2yeby@b1hb)hbXb2yeb@,tb&bQ<b1=Y_1VQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQ.v%%Fms["*s[.v"*\\^2d"\"%s"*\\^2d"\"")Qs["=Y.v+*"*\\^2Q"\"*3]"*\\^2Q"\"Q\YuyFYHpQ)

Requiere cualquier entrada no vacía, pero su valor no se utiliza.

Explicación (para la versión nueva y de puntuación razonable ):

=QC`.pG                   Sets the value of the autofill variable to app. 256^27!  
                                  27! ~= the number of characters in the string
                                  containing all permutations of the alphabet. 
                                  We interpret that string as a base-256 number.
       L                  Define a function y(b,global Q):
        &=^QQ             Set Q to Q^Q and:
        ?+Ibt]0           If (?) the variable (b) is (I)nvariant on (+)adding itself
                             to the empty array (i.e. if it's an array itself):
               ?htb        If the second element of b is not 0:
                   ?eb         If the last element is not 0
                       [Xb2yeby@b1hG)   return [b with its last element replaced with y(b[-1]), y(b[1]), b[0]]
                     hb                 else return b[0]
                 Xb2yeb     else return b with its last element replaced with y(b[-1])
           @,tb&bQ<b1      If b isn't an array,return:
                               either b-1 if it's a standard ordinal (1 or more)
                               or Q if b is ω
                               or 0 if b is 0
 =Y_1                          Set the global variable Y to -1 (representing ω)
 VQ                        Q times, do (the rest of the explanation):
  VQVQ....VQ               Iterate from 0 to Q-1 183 times, each subiteration
                              reading the most recent value of Q when it starts:
  .v%%Fms["*s[.v"*\\^2d"\"%s"*\\^2d"\"")Q
                            Iterate from 0 to Q-1 Q times, each subiteration 
                               reading the most recent value of Q when it starts:                        
 s["=Y.v+*"*\\^2Q"\"*3]"*\\^2Q"\"Q
                             Y = [Y,Y,Y] Q times, stacking with previous iterations.
 uyFYHpQ)                    Run y_x(Y) for x incrementing until y_(x-1)(Y)=0

Es muy difícil para mí calcular el tamaño de esto, principalmente porque es tarde en el día y no estoy muy familiarizado con las jerarquías de rápido crecimiento o cómo trataría de averiguar cuántas veces Q pasa por el proceso. y()escurridor. Si bien ahora sé más sobre los ordinales, todavía no tengo idea de cómo calcular el valor del ordinal representado por la definición recursiva en mi programa. Me uniría al servidor Discord, pero bajo un seudónimo preferiría no estar vinculado a mi nombre real.

Desafortunadamente, debido a que sé relativamente poco sobre dichas jerarquías de rápido crecimiento, es probable que ya haya perdido la respuesta de Ruby. Es difícil para mí decirlo. Puede que haya superado la respuesta de Ruby, pero no estoy 100% seguro. ¯ \ _ (ツ) _ / ¯

Steven H.
fuente
Si entiendo correctamente, su puntaje probablemente esté en algún lugar en el estadio de 27^^^27^^27^^4, o f<sub>4</sub>(27^^27^^4)) ≈ f<sub>4</sub>(f<sub>3</sub>(f<sub>3</sub>(19))).
Simplemente hermoso arte
Hice un pequeño cambio que debería haber pensado ayer, pero de alguna manera no lo hice, haciendo que yrecurse para operar en y(Q-1)lugar de operar solo Q. ¿Cómo afecta esto al puntaje?
Steven H.
1
No estoy completamente seguro de lo que está pasando. ¿ y(Q) = L(y(Q-1))Per se?
Simplemente hermoso arte
1
Creo que tendremos mejor suerte haciendo esto en una sala de chat .
Steven H.
@SimplyBeautifulArt Probablemente sea mejor no usar la notación de jerarquía de rápido crecimiento para esto, ya que es un poco pequeña.
PyRulez
3

Pyth, f 3 + σ -1 + ω 2 (256 26 )

Donde σ m [n] es la Busy Beaver función Σ de orden mllamada en n: σ m [n] = Σ m (n). El orden -1es denotar que el Busy Beaver aquí no se llama en una verdadera máquina de Turing, sino más bien una aproximación con una cinta de Qelementos de envoltura finita . Esto permite que el problema de detención sea solucionable para estos programas.

=QCGM.x-Hlhf!-/T4/T5.__<GH0M.x+Hlhf!-/T4/T5._>GHlGL=.<QC`m.uX@[XN2%h@N2l@N1XN2%t@N2l@N1XN1X@N1@N2%h@@N1@N2l@N1XN1X@N1@N2%t@@N1@N2l@N1XW!@@N1@N2N2nFKtPNXW@@N1@N2N2gFK)@hNeN3%heNlhNd)bLym*F[]d^UQQUQUld)^U6QJ"s*].v*\mQ"
.v+PPPP*JQ"+*\mQ\'

El TL; DR es que esto crea todos los posibles programas BrainF ** k de longitud Q, los ejecuta en un entorno donde el valor máximo de un número entero es Q y la longitud de la cinta es Q, y compila todos los estados de estas operaciones juntos para agregue (ese es el 3+) a Q, repitiendo lo anterior en una escala de f ω 2 .

Todavía tengo ~ la mitad de los personajes con los que trabajar si quisiera hacer algo más, pero hasta que descubramos dónde está, lo dejaré como está.

Steven H.
fuente
Hice una explicación mucho mejor de σ en la tabla de clasificación.
Simplemente hermoso arte
44
No me parece que esta función Busy Beaver en particular crezca tan rápido. Con un límite de Q enteros entre 0 y Q, solo hay (Q + 1) ^ Q posibles cintas, y Q posibles posiciones en el programa, por lo que puede haber como máximo Q * (Q + 1) ^ Q posibles estados de Un programa en ejecución. Por lo tanto, un programa debe detenerse dentro de Q * (Q + 1) ^ Q pasos o nada en absoluto. El número de posibles programas también está limitado por un límite superior exponencial. Entonces, me parece que esta función Busy Beaver tiene un límite superior exponencial, y la función final será del orden de $ f _ {\ omega ^ 2} $.
Deedlit
2

python, f 3 (f 3 (141)), 512 bytes

import math
def f(x):
    return math.factorial(x)  
x=9
for j in range(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(x))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))):
    x=f(x)
print x

Esta no es realmente una respuesta válida, pero quería publicarla de todos modos. Un resumen rápido:

import math # imports the factorial function
def f(x):
    return math.factorial(x) # shortens the factorial operation
x=9 # sets x to highest available number
for j in range(f(...f(x)...)): # repeats * A LOT *
    x=f(x) # does the factorial of x
print x # outputs the result

De todos modos, no sé si esta respuesta es técnicamente legal, pero fue divertido escribirla. Siéntase libre de editar cualquier error que encuentre en el código.

yo..
fuente
Creo que esto es f_3 (9), y definitivamente es legal. Sin for j in range(f(x)): for j in range(f(x)): x = f(x)embargo, obtendría un número mucho mayor al anidar . ¡Únete a nosotros en el chat para discutir por qué!
Steven H.
¿Por qué no es una respuesta válida?
Simply Beautiful Art
No entendí bien la pregunta, así que hice lo que pensé que era correcto.
yo ..
1

Ruby, probablemente ~ f ω + 35 (9 9 99 )

G=->n,k{n<1?k:(f=->b,c,d{x=[]
c<G[b,d]?b-=1:(x<<=b;c-=G[b,d])while c>=d
x<<[c]}
x=f[n-1,k,b=1]
(b+=1;*u,v=x;x=v==[0]?u:v==[*v]?u<<[v[0]-1]:u+f[n-1,G[v,b]-1,b])while x[0]
b)};(n=9**9**99).times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n=G[n,n]}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}};p n

Pruébalo en línea!

Explicación matemática aproximada:

El siguiente es aproximadamente igual al programa anterior, pero simplificado para que sea más fácil de entender.

G(0,k) = k Es nuestra función base.

Para evaluar G(n,k), lo tomamos ky lo escribimos como G(n-1,1) + ... + G(n-2,1) + ... + G(0,1).

Luego cambie todas las G(x,1)'s en G(x,2)' s y reste 1del resultado completo.

Vuelva a escribirlo en la forma anterior usando G(x,2), donde x<n, y deje el resto al final. Repetir, cambiar G(x,2)a G(x,3), etc.

Cuando llegue el resultado -1, devuelve la base (la bque estaría en G(x,b)).

Ejemplos:

G (1,1):

1: 1 = G(0,1)
2: G(0,2) - 1 = 1
3: 1 - 1 = 0
4: 0 - 1 = -1      <----- G(1,1) = 4

G (1,2):

1: 2 = G(0,1) + G(0,1)
2: G(0,2) + G(0,2) - 1 = G(0,2) + 1
3: G(0,3) + 1 - 1 = G(0,3)
4: G(0,4) - 1 = 3
5: 3 - 1 = 2
6: 2 - 1 = 1
7: 1 - 1 = 0
8: 0 - 1 = -1      <----- G(1,2) = 8

G (1,3):

1: 3 = G(0,1) + G(0,1) + G(0,1)
2: G(0,2) + G(0,2) + G(0,2) - 1 = G(0,2) + G(0,2) + 1
3: G(0,3) + G(0,3)
4: G(0,4) + 3
5: G(0,5) + 2
6: G(0,6) + 1
7: G(0,7)
8: 7
9: 6
10:5
11:4
12:3
13:2
14:1
15:0
16:-1      <----- G(1,3) = 16

G (2,5):

1: 5 = G(1,1) + G(0,1)
2: G(1,2) + 1
3: G(1,3)
4: G(0,4) + G(0,4) + G(0,4) + G(0,4) + G(0,4) + G(0,4) + G(0,4) + 3
5: G(0,5) + G(0,5) + G(0,5) + G(0,5) + G(0,5) + G(0,5) + G(0,5) + 2
6: G(0,6) + G(0,6) + G(0,6) + G(0,6) + G(0,6) + G(0,6) + G(0,6) + 1
...
1024: -1      <----- G(2,5) = 1024

Haciendo algunos cálculos, descubrí que

G(1,n-1) = 2ⁿ
G(2,n+6) ~ 2^G(2,n),  large enough n.

Y más allá de eso, tiende a ponerse un poco peludo.

En general, tenemos

G(n,k+G(n-1,1)) ~ G(n-1,G(n,k)), large enough n.
Simplemente hermoso arte
fuente
1

Python 3, f ω ω + ω * ω (9 9 9 99 )

from functools import*
h=lambda a,x,b:h(h(a,x,b-1),x-1,a)if x*b else a+b
def f(*x):
    if(any(x[:2]):return reduce(lambda y,z:h(z,y,f(x[0],x[1]-1,*x[2:])),x[::-1])if x[0]*x[1]else(f(x[0]-1,f(x[0]-1,x[0],*x[2:]))if x[0]>x[1]else(f(x[1]-1,f(*([x[1]-1]*2+x[2:])),*x[2:])))
    for a,k in enumerate(x):if k:return f(*[f(*[k]*a,k-1,*x[a+1:])]*a,k-1,*x[a+1:])
    return 0
x,s,g,e,r,z=9**9**9**99,"f(*[%s]*%s)",lambda a,b:a%((b,)*a.count("%")),"x*=eval(\"%s\");","x","x=g(e,g(reduce(g,[s]*x,s),r));"
print(exec(z*x)or eval(r))

Tendré una explicación pronto.

Steven H.
fuente
1

Python 3 , ~ f ε 0 (9 9 9 )

N=9**9**9
def f(a,n):
 if a[0]==[]:return a[1:]
 if a[0][0]==[]:return[a[0][1:]]*n+a[1:]
 return [f(a[0],n)]+a[1:]
a=eval("["*N+"]"*N)
n=2
while a:a=f(a,n);n+=1
print(n)

Pruébalo en línea!

Monja permeable
fuente
N = 9 ** 9e99 debería ser un poco más grande
febrero
que la respuesta de quién?
Leaky Nun
Quiero decir que si reemplaza el primer me gusta con N = 9 ** 9e99, la salida debería ser un poco más grande porque 9e99> 9 ** 9. Por supuesto, sigue siendo tu respuesta.
fejfo
@fejfo Quiero decir que no cambiaría mi clasificación.
Leaky Nun
2
¿Eso importa?
fejfo
1

Python 3, 323 bytes, g 9e9 (9)

exec("""a=`x:9**x
n=`a,f:`x:a and n(a-1,f)(f(x))or x
c=`n:`l:l[~n](l)
e=`x:n(x,c(0))([x,`l:[a(l[0]),n(*l)],c(0),`l:[a(l[0]),l[2](l[:2])[1]]+map(`i:l[1]((l[0],i))[1],l[2:])]+list(map(c,range(a(x),1,-1))))[1]
f=`l:[l[1](l[0]),e(l[1](l[0]))(l)[1]]
g=`x:e(x)((x,f))[1]((x,a))[1](x)
print(n(9e9,g)(9))""".replace('`','lambda '))

Pruébalo en línea!

Explicación

Python 3 es un lenguaje verdaderamente recursivo, esto significa que una función no solo puede llamarse a sí misma, sino que también puede tomar otras funciones como funciones de entrada o salida. El uso de funciones para mejorar es en lo que se basa mi programa.

f = lambda x, a: [a (x), e (x) ((x, a)) [1]]

Definición

a(x)=9^x
b(x,f)=a(x), f^x
c(n)(*l)=l[~n](l)
c(0)=c0 <=> c0(…,f)=f(…,f)
d(x,b,c,*l)=a(x), c0(x,b), b(x,c0), b(x,f) for f in l
e(x)=c0^x(x,b,c0,d,c(a(x)),c(a(x)-1),c(a(x)-2),…,c(3),c(2),c(1))[1] 
f(x,a)=a(x),e(a(x))(x,a)[1](x)
g(x)=e(x)(x,f)[1](x,a)[1](x)
myNumber=g^9e9(9)

Definición explicada

a(x)=9^x a es la función base, elegí esta función porque x> 0 => a (x)> x` que evita puntos fijos.

b(x,f)=a(x), f^xb es la función de mejora general, toma cualquier función y genera una mejor versión de la misma. b incluso se puede aplicar a sí mismo:b(x,b)[1]=b^x b(x,b^x)[1]=b^(x*x)

pero para usar completamente el poder de bmejorar bnecesita tomar la salida de b y usarla como la nueva b, esto es lo que hace c0:

c0(…,f)=f(…,f)
c0(x,b^x)=b^x(x,b^x)[1]>b^(9↑↑x)

la función c (n) más general toma el último argumento n (comenzando desde 0) so c(1)(…,f,a)=f(…,f,a)y c(2)(…,f,a,b)=f(…,f,a,b). *lsignifica que l es una matriz y l[~n]toma el último argumento n

d(x,b,c,*l)=a(x), c0(x,b), b(x,c0), b(x,f) for f in ld usa c0 para actualizar byb para actualizar todas las demás funciones de entrada (de las cuales puede haber cualquier cantidad debido a la lista)
d(x,b,c,d)>9^x,b^x,c^x,d^xyd²(x,b,c,d)>a²(x), b^(9↑↑x), c^(9↑↑x), d^(9↑↑x)

pero d se pone aún mejor si lo combinas con c:
c0²(x,b,c0,d)=d^x(9^x,b^x,c0^x,d^x)=… c0(x,b,c0,d,c1)=c1(x,b,c0,d,c1)=d(x,b,c0,d,c1)=9^x,b^x,c0^x,d^x,c1^x c0²(x,b,c0,d,c1)=c0(9^x,b^x,c0^x,d^x,c1^x)=c1^x(9^x,b^x,c0^x,d^x,c1^x)=…

cuanto más c (x) agregue al final, más poderoso se vuelve. El primer c0 siempre permanece d: c0(x,b,c0,d,c4,c3,c2,c1)=c1(…)=c2(…)=c3(…)=c4(…)=d(x,b,c0,d,cX,cX-1,…,c3,c2,c1)=…
pero el segundo deja versiones iteradas:

c0²(x+1,b,c0,d,c4,c3,c2,c1)
=c0(9^x+1,b^x+1,c0^x+1,d^x+1,c4^x+1,c3^x+1,c2^x+1,c1^x+1)
=c1^x(c2^x(c3^x(c4^x(d^x(9^x+1,b^x+1,c0^x+1,d^x+1,c4^x+1,c3^x+1,c2^x+1,c1^x+1)))))

Cuando d^xfinalmente se calcula c4tomará una versión mucho más iterada de dla próxima vez. Cuando c4^xfinalmente se calcula c3tomará una versión mucho más iterada de c4...
Esto crea una versión realmente potente de iteración porque d:

  1. Mejora el busoc0
  2. Mejora el c0usob
  3. Mejora todas las capas de anidamiento usando b Las mejoras mejoran, esto significa que d se vuelve más poderoso cuando se itera más.

Crear esta larga cadena de c es lo que e(x)=c0^x(x,b,c0,d,c(a(x)),c(a(x)-1),c(a(x)-2),…,c(3),c(2),c(1))[1]hace.
Se usa c0^xpara evitar eso c0que simplemente daría d.
Esto [1]significa que eventualmente devolverá la segunda salida de d^…. Por lo tanto b^….

En este punto, no podía pensar en nada que hacer con e (x) para aumentar significativamente su salida, excepto aumentar la entrada.

Entonces f(x,a)=a(x),e(a(x))(x,a)[1](x)usa el b^…generado por e(x)para generar una mejor función base y usa esa función base para llamar e(x)con una entrada más grande.

g(x)=e(x)(x,f)[1](x,a)[1](x)usa un final e(x)para anidar fy produce una función realmente poderosa.

Aproximación fgh

Necesitaré ayuda para aproximar este número con cualquier tipo de fgh.

Versión anterior : f ω ω 6 (f ω ω 5 (9e999)), ¡ Pruébelo en línea! Historial de revisión de explicación

fejfo
fuente
En realidad, f_1(x) = x+xpero a la larga, esto no importa demasiado.
Simplemente hermoso arte
¿Podría explicar sus secuencias fundamentales un poco más?
Simplemente hermoso arte
@SimplyBeautifulArt porque sí, olvidé actualizarlo después de cambiarlo x*x.
fejfo
@SimplyBeautifulArt Mi respuesta no utiliza ningún ordinal, por lo que me resulta difícil explicarlo con ordinales. Todo lo que realmente puedo hacer es dar la definición de mis funciones y una aproximación del efecto en fgh. Ejemplo:a2(f_n)~=f_{n+1}
fejfo
1

Ruby, f ε 0 2 (5), 271 bytes

m=->n{x="";(0..n).map{|k|x+="->f#{k}{"};x+="->k{"+"y=#{n<1??k:"f1"};k.times{y=f0[y]};y";(2..n).map{|l|x+="[f#{l}]"};eval x+(n<1?"":"[k]")+"}"*(n+2)}
g=->z{t="m[#{z}]";(0...z).map{|j|t+="[m[#{z-j-1}]]"};eval t+"[->n{n+n}][#{z}]"}
p m[5][m[4]][m[3]][m[2]][m[1]][m[0]][g][6]

Pruébalo en línea!

Esto se basa en el mapa m (n) .

Explicación:

m[0][f0][k] = f0[f0[...f0[k]...]]con kiteraciones de f0.

m[1][f0][f1][k] = f0[f0[...f0[f1]...]][k]con kiteraciones de f0.

m[2][f0][f1][f2][k] = f0[f0[...f0[f1]...]][f2][k]con kiteraciones de f0.

En general, m[n]toma en n+2argumentos, itera el primer argumento, f0, kveces sobre el segundo argumento, y luego se aplica la función resultante sobre el tercer argumento (si existe), a continuación, se aplica la función resultante en el cuarto argumento (si existe), etc.

Ejemplos

m[0][n↦n+1][3] = (((3+1)+1)+1 = 6

En general m[0][n↦n+1] = n↦2n,.

m[0][m[0][n↦n+1]][3] = m[0][n↦2n][3] = 2(2(2(3))) = 24

En general m[0][m[0][n↦n+1]] = n↦n*2^n,.

m[1][m[0]][3]
= m[0][m[0][m[0][n↦n+1]]][3]
= m[0][m[0][n↦2n]][3]
= m[0][n↦n*2^n][3]
= (n↦n*2^n)[(n↦n*2^n)[n↦n*2^n(3)]]
= (n↦n*2^n)[(n↦n*2^n)[24]]
= (n↦n*2^n)[402653184]
= 402653184*2^402653184

En general, m[1][m[0]][n↦n+1] = f_ωen la jerarquía de rápido crecimiento.


g[z] = m[z][m[z-1]][m[z-2]]...[m[1]][m[0]][n↦2n][z]

y el resultado final es

m[5][m[4]][m[3]][m[2]][m[1]][m[0]][g][6]
Simplemente hermoso arte
fuente