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

47

La función TREE (k) da la longitud de la secuencia más larga de árboles T 1 , T 2 , ... donde cada vértice está etiquetado con uno de los k colores, el árbol T i tiene como máximo i vértices, y ningún árbol es un menor de cualquier árbol que lo siga en la secuencia.

ÁRBOL (1) = 1, con, por ejemplo, T 1 = (1).

ÁRBOL (2) = 3: por ejemplo, T 1 = (1); T 2 = (2)--(2); T 3 = (2).

ÁRBOL (3) es un gran gran número. Incluso más grande que el número de Graham. ¡Su trabajo es generar un número aún mayor !

Este es un por lo que el objetivo es escribir el programa más corto en cualquier idioma que arroje de manera determinista un número mayor o igual a TREE (3) (para el stdout).

  • No está permitido tomar aportaciones.
  • Su programa finalmente debe terminar, pero puede suponer que la máquina tiene memoria infinita.
  • Puede suponer que el tipo de número de su idioma puede contener cualquier valor finito, pero necesita explicar cómo funciona exactamente en su idioma (por ejemplo: ¿un flotador tiene una precisión infinita?)
    • No se permiten infinitos como salida.
    • El flujo inferior de un tipo de número produce una excepción. No se envuelve.
  • Debido a que TREE (3) es un número tan complejo, puede usar la aproximación jerárquica de rápido crecimiento f ϑ (Ω ω ω) +1 (3) como el número a batir.
  • Debe proporcionar una explicación de por qué su número es tan grande y una versión no codificada de su código para verificar si su solución es válida (ya que no hay una computadora con suficiente memoria para almacenar TREE (3) )

Nota: Ninguna de las respuestas Actualmente encontró aquí el trabajo.

¿Por qué es TREE (3) tan grande?

PyRulez
fuente
99
@StepHen no es trivally. Llegar al árbol (3) requiere un paradigma completamente nuevo.
PyRulez
11
TREE(3)+1allí gano
HyperNeutrino
1
@KSmarts ¿Te das cuenta de que ninguna de las respuestas se acerca a TREE (3)?
Simplemente hermoso arte
2
@MDXF Voy a decir que no, porque usar INT_MAX es una especie de trampa (de lo contrario, imprimir INT_MAX ganaría instantáneamente). En general, su salida debe ser la misma para cualquier sistema suficientemente grande.
PyRulez

Respuestas:

38

Nuevo Ruby, 135 bytes, >> H ψ (φ 3 (Ω + 1)) (9)

donde H es la jerarquía Hardy, ψ es una versión extendida del OCF de Madore (se explicará a continuación) y φ es la función Veblen.

Pruébalo en línea!

f=->a,n,b=a{c,d,e=a;a==c ?a-1:e ?a==a-[0]?[[c,d,f[e,n,b]],d-1,c]:c:[n<1||c==0?n:[f[c||b,n-1]],n,n]};h=[],k=9,k;h=f[h,p(k*=k)]while h!=0

Ungolfed: (usando funciones, no lambdas)

def f(a,n,b)
  c,d,e = a
  if a == c
    return a-1
  elsif e
    if a == a-[0]
      return [[c,d,f(e,n,b)],d-1,c]
    else
      return c
    end
  else
    x = c || b
    if n < 1 || c == 0
      return [n,n,n]
    else
      return [f(x,n-1,x),n,n]
    end
  end
end

k = 9
h = [[],k,k]
while (h != 0) do
  k *= k
  p k
  h = f(h,k,h)
end

OCF extendido de Madore:

ingrese la descripción de la imagen aquí

Y (groseramente) la función phi de Veblen:

ingrese la descripción de la imagen aquí

Explicación sin ordinales:

f(a,n,b) reduces an array recursively. (if no third argument given, it takes the first argument twice.)
f(k,n,b) = k-1, k is a positive int.
f([c,d,0],n,b) = f([c,0,e],n,b) = c
f([c,d,e],n,b) = [[c,d,f(e,n,b)],d-1,c], d ≠ -1 and c ≠ 0

f([a],0,b) = [0,0,0]
f([0],n,b) = [n,n,n]
f([],n,b) = f([b],n,b)
f([a],n,b) = [f[a,n-1,a],n,n]

Mi programa inicia k = 9, h = [[],9,9]. Luego aplica k = k*ky h = f(h,k)hasta h == 0y salidas k.

Explicación con ordinales:

Ordinals follow the following representation: n, [], [a], [a,b,c], where n,d is a natural number and a,c are all ordinals.
x = Ord(y) if y is the syntactic version of x.
a[n,b] = Ord(f(a,n))
ω = Ord([0]) = Ord(f([a],-1,b))
n = Ord(n)
Ω = Ord([])
ψ'(a) = Ord([a])
ψ'(a)[n] = Ord(f([a],n))
φ(b,c) ≈ Ord([[0],b,c])
a(↓b)c = Ord([a,b,c]) (down-arrows/backwards associative hyper operators I designed just for ordinals)

We follow the following FS for our ordinals:
k[n,b] = k-1, k < ω
ω[n,b] = n(↓n)n
(a(↓b)0)[n,b] = (a(↓0)c)[n,b] = a
(a(↓b)c)[n,b] = (a(↓b)(c[n,b]))(↓b[n,b])a, b ≥ 0 and c > 0.
ψ'(a)[0,b] = 0(↓0)0
ψ'(a)[n,b] = (ψ'(a[n-1,a]))(↓n)ω, a > 0 and n ≥ 0. (also note that we've changed from [n,b] to [n,a].)
Ω[n,b] = ψ'(b)[n,b]

ψ '(ω ∙ α) ≈ ψ (α), la función de colapso ordinal descrita en la imagen de arriba.

Mi programa se inicia más o menos k = 9y h = Ω(↑9)9, luego, se aplica k ← k²y h ← h[k,h]hasta h = 1y vuelve k.

Entonces, si hice esto bien, [[],9,9]es mucho más grande que el ordinal de Bachmann-Howard ψ (Ω Ω Ω ... ), que es mucho más grande que ϑ (Ω ω ω) +1.

ψ (Ω (↓ 9) 9)> ψ (Ω (↓ 4) 3)> ψ (Ω Ω Ω ) +1> ψ (Ω Ω ω ω ) +1> ϑ (Ω ω ω) +1

Y si mi análisis es correcto, entonces deberíamos tener ψ '(Ω Ω ∙ x) ~ = ψ * (Ω Ω ∙ x), donde ψ * es la función psi normal de Madore. Si esto se cumple, entonces mi ordinal es aproximadamente ψ * (φ 3 (Ω + ω)).


Old Ruby, 309 bytes, H ψ ' 09 ) (9) (ver historial de revisiones , además el nuevo es mucho mejor)

Simplemente hermoso arte
fuente
1
Solo podía probar mi programa con muy pocos valores, así que discúlpeme si me he equivocado en alguna parte.
Simplemente hermoso arte
1
Bleh, lenta pero segura, tratando de pensar y arreglar todo lo que veo mal. :-( Muy tedioso.
Simplemente hermoso arte
1
Hmm ... entonces $ f_ {ψ_0 (ψ9 (9))} (9) $ significa que necesitamos al menos el nivel cardinal débilmente inaccesible de $ ψ_9 (9) $ th de la jerarquía de rápido crecimiento con base 9 para ser mayor que $ ÁRBOL (3) $
Secreto
1
@Secret No, solo quería rebasar un poco, además, calcular un valor más cercano a TREE (3) me costaría más bytes para escribir. Y no hay cardenales inaccesibles utilizados aquí.
Simplemente hermoso arte
1
Nitpicks de golf: definitivamente puedes jugar al golf a.class!=Array, lo más idiomático es !a.is_a? Arraypero lo más corto que se me ocurre a!=[*a]. Y los métodos se pueden convertir en lambdas: f=->a,n=0,b=a{...}...f[x,y]para guardar algunos caracteres y quizás abrir posibilidades de refactorización usándolos como objetos de primera clase.
histocrat
23

Haskell, 252 Bytes, ÁRBOL (3) +1

data T=T[T]Int
l(T n _)=1+sum(l<$>n)
a@(T n c)#T m d=any(a#)m||c==d&&n!m
l@(x:t)!(y:u)=l!u||x#y&&t!u
x!_=null x
a n=do x<-[1..n];T<$>mapM(\_->a$n-1)[2..x]<*>[1..3]
s 0=[[]]
s n=[t:p|p<-s$n-1,t<-a n,(l t<=n)>any(#t)p]
main=print$[x|x<-[0..],null$s x]!!0

¡Gracias por la ayuda de H.PWiz, Laikoni y Ørjan Johansen por ayudar a jugar el código!

Según lo sugerido por HyperNeutrino , mi programa genera TREE (3) +1, exactamente (TREE es computable como resulta).

T n ces un árbol con etiqueta cy nodos n. cdebe ser 1, 2o 3.

l tes el número de nodos en un árbol t.

t1 # t2es verdadero si se t1integra homeomórficamente en t2(basado en la definición 4.4 aquí ), y falso de lo contrario.

a nsaca una gran lista de árboles. La lista exacta no es importante. La propiedad importante es que a ncontiene todos los árboles hasta nnodos, con nodos están etiquetados con 1, 2, o 3, tal vez algunos árboles y más también (pero esos otros árboles también se pueden marcar con 1, 2o 3). También se garantiza la salida de una lista finita.

s nenumera todas las secuencias de longitud nde los árboles, de modo que el reverso (ya que lo construimos al revés) de esa secuencia es válido. Una secuencia es válida si el enésimo elemento (donde comenzamos a contar en 1) tiene como máximo n nodos, y ningún árbol se inserta homeomórficamente en uno posterior.

mainimprime el más pequeño de nmodo que no haya secuencias válidas de longitud n.

Como TREE(3)se define como la longitud de la secuencia válida más larga, TREE(3)+1es la más pequeña, de nmodo que no hay secuencias válidas de longitud n, que es lo que genera mi programa.

PyRulez
fuente
16

Python 2, 194 bytes, ~ H ψ (Ω Ω Ω ) (9)

donde H es la jerarquía de Hardy y ψ es la función de colapso ordinal debajo del ordinal de Bachmann-Howard definido por Pohlers.

Gracias a Jonathan Frech por -3 bytes.

def S (T): devuelve 0 si T == 1else [S (T [0])] + T [1:]
def R (T): U = T [0]; V = T [1:]; exec "global B; B = T" * (T [-1] == 0); retorno [S (B)] + V si U == 1else [R (U)] * c + V si U más V
A = [[[1,1], 1], 0]
c = 9
mientras que A: A = R (A); c * = c
imprimir c

Pruébalo en línea!

Versión mejor espaciada:

def S (T):
  devuelve 0 si T == 1 más [S (T [0])] + T [1:]

def R (T):
  U = T [0]
  V = T [1:]
  B global
  si T [-1] == 0:
    B = T
  si U == 1: 
    volver [S (B)] + V
  volver [R (U)] * c + V si U más V

A = [[[1,1], 1], 0]
c = 9
mientras que A:
  A = R (A)
  c * = c
imprimir c

Explicación:

Este programa implementa una variante de la hidra Buchholz , usando solo etiquetas de 0 y 1. Básicamente, en cada paso, observamos el primer nodo de hoja del árbol y vemos si está etiquetado con un 0 o un 1.

-Si el nodo hoja está etiquetado con un 0, eliminamos el nodo hoja y luego copiamos el árbol comenzando por el padre del nodo hoja c veces, todas las copias conectadas al abuelo del nodo hoja.

-Si el nodo de la hoja está etiquetado con un 1, entonces buscamos hacia la raíz hasta llegar a un nodo ancestro etiquetado con un 0. Sea S el árbol que comienza desde ese nodo ancestro. Supongamos que S 'sea S con el nodo hoja reetiquetado con 0. Reemplace el nodo hoja con S'.

Luego repetimos el proceso hasta que no nos quede más que el nodo raíz.

Este programa difiere del procedimiento normal de hidra de Buchholz de dos maneras: primero, después de realizar el procedimiento anterior, recurrimos de nuevo al árbol y realizamos el procedimiento de copia de la etiqueta 0 descrito anteriormente para cada nodo ancestro del nodo hoja original. Esto aumenta el tamaño del árbol, por lo que nuestro procedimiento tomará más tiempo que la hidra normal de Buchholz y, por lo tanto, conducirá a un número mayor al final; sin embargo, aún terminará porque el ordinal asociado con el nuevo árbol seguirá siendo menos el viejo árbol. La otra diferencia es que, en lugar de comenzar con c = 1 y aumentar 1 cada vez, comenzamos con c = 9 y lo cuadramos cada vez, porque ¿por qué no?

El árbol [[[1,1], 1], 0] corresponde al ordinal ψ (Ω Ω Ω ), que es considerablemente más grande que el ordinal ϑ (Ω ω ω), y por lo tanto nuestro número final resultante de aproximadamente H ψ (Ω Ω Ω ) (9) definitivamente excederá el ÁRBOL (3).

Deedlit
fuente
No tan golfista mi amigo :-)
Simplemente hermoso arte
Lo sé. No sé cómo reducirlo aún más, al menos no en Python. Tal vez pueda intentar aprender algo de Ruby.
Deedlit
¿Es posible poner R (T) todo en una línea?
Simplemente hermoso arte
@SimplyBeautifulArt Probablemente sí ( enlace TIO ), aunque no probado.
Jonathan Frech
@ JonathanFrech ¡Gracias por tu ayuda! Desafortunadamente, cuando probé su código me dio un mensaje de error "global B no está definido". No tengo idea de por qué esto da un error mientras que el código original no, así que no sé cómo solucionarlo.
Deedlit
6

Rubí, 140 bytes, ~ H ψ (Ω Ω Ω ) (81)

donde H es la jerarquía Hardy y ψ es la función de colapso ordinal estándar debajo del ordinal de Bachmann-Howard, como se define aquí .

s=->t{*v,u=t;t==1?[]:v<<s[u]}
r=->t{*v,u=t;$b=t[0][0]?$b:t;u==1?v<<s[$b]:u[0]?v+[r[u]]*$c:v}
$c=9
a=[],[1,[1,1]]
($c*=9;a=r[a])while a[0]
$c

Pruébalo en línea!

Versión sin golf:

def S (a)
  * v, u = a
  si a == 1 
    regreso []
  más
    volver v + [S (u)]
  fin
fin  

def R (t)
  * v, u = t
  si t [0] == []
    $ b = t
  fin
  si u == 1
    retorno v + [S ($ b)]
  elsif u == []
    volver v
  más
    devuelve v + [R (u)] * $ c
  fin
fin

$ c = 9

a = [[], [1, [1,1]]]

mientras que a! = [] do
  $ c * = 9
  a = R (a)
fin

imprimir $ c

Este programa implementa la hidra Buchholz con nodos etiquetados con [] 's y 1's, como se describe en mi entrada de Python 2.

El árbol [[], [1, [1,1]]] corresponde al ordinal ψ (Ω Ω Ω ), que es considerablemente más grande que el ordinal ϑ (Ω ω ω) = ψ (Ω Ω ω ω ), y entonces nuestro número final resultante de aproximadamente H ψ (Ω Ω Ω ) (81) excederá el ÁRBOL (3).

Deedlit
fuente
Dang it you and your 149 bytes.
Simplemente hermoso arte
Pero Ruby por la victoria: P
Simply Beautiful Art
Golpe de golf: en lugar de escribir u==0?v:u==[]?v, podrías escribir u==0?||u[0]?v, lo que ahorra dos bytes.
Simplemente hermoso arte
@SimplyBeautifulArt ¡Gracias por la ayuda! Pelotas de vuelta en tu cancha. : D
Deedlit
2
D: <esa diferencia de 1 byte entre nosotros es la cosa más frustrante de la historia.
Simplemente hermoso arte
6

Julia, 569 bytes, número del cargador

r,/,a=0,div,0;¬x=x/2;r<s=r?s:0;y\x=y-~y<<x;+x=global r=(x%2!=0)<1+(+¬x);!x=¬x>>+x;√x=S(4,13,-4,x);S(v,y,c,t)=(!t;f=x=r;f!=2?f>2?f!=v?t-(f>v)%2*c:y:f\(S(v,y,c,!x)\S(v+2,t=√y,c,+x)):S(v,y,c,!x)$S(v,y,c,+x));y$x=!y!=1?5<<y\x:S(4,x,4,+r);D(x)=(c=0;t=7;u=14;while(x!=0&&D(x-1);(x=¬x)%2!=0)d=!!D(x);f=!r;x=!r;c==r<((!u!=0||!r!=f||(x=¬x)%2!=0)<(u=S(4,d,4,r);t=t$d);¬f&(x=¬x)%2!=0<(c=d\c;t=√t;u=√u));(c!=0&&(x=¬x)%2!=0)<(t=((~u&2|(x=¬x)%2!=0)<(u=1<<(!c\u)))\(!c\t);c=r);¬u&(x=¬x)%2!=0<(c=t\c;u=√t;t=9)end;global a=(t\(u\(x\c)))\a);D(D(D(D(D(BigInt(99))))))

Para ahorrarme un poco de trabajo preliminar, decidí portar Loader.c a Julia casi uno por uno y compactarlo en el bloque de código anterior. Para aquellos que quieran hacer las comparaciones ellos mismos (ya sea para verificar mi puntuación o para ayudarme a encontrar errores o mejorar mi código), a continuación se encuentra una versión sin golf:

r,/,a=0,div,0;
¬x=x/2;
r<s=r?s:0;
y\x=y-~y<<x;
+x=global r=(x%2!=0)<1+(+¬x);
!x=¬x>>+x;
√x=S(4,13,-4,x);
S(v,y,c,t)=(
    !t;
    f=x=r;
    f!=2?
        f>2?
            f!=v?
                t-(f>v)%2*c
                :y
            :f\(S(v,y,c,!x)\S(v+2,t=√y,c,+x))
        :S(v,y,c,!x)$S(v,y,c,+x)
);
y$x=!y!=1?5<<y\x:S(4,x,4,+r);
D(x)=(
    c=0;
    t=7;
    u=14;
    while(x!=0&&D(x-1);(x=¬x)%2!=0) 
        d=!!D(x);
        f=!r;
        x=!r;
        c==r<(
            (!u!=0||!r!=f||(x=¬x)%2!=0)<(
                u=S(4,d,4,r);
                t=t$d
            );
            ¬f&(x=¬x)%2!=0<(
                c=d\c;
                t=√t;
                u=√u
            )
        );
        (c!=0&&(x=¬x)%2!=0)<(
            t=((~u&2|(x=¬x)%2!=0)<(u=1<<(!c\u)))\(!c\t);
            c=r
        );
        ¬u&(x=¬x)%2!=0<(
            c=t\c;
            u=√t;
            t=9
        )
    end;
    global a=(t\(u\(x\c)))\a
);
D(D(D(D(D(BigInt(99))))))

No hay conteos anteriores porque hice demasiados errores de bytes en el golf agresivo que he hecho.

eaglgenes101
fuente
1
Oh querido. Una adición más a esta locura de un lugar.
Simplemente hermoso arte
1
Además, aunque no tengo pruebas de esto, creo que D (D (D (D (99))))) es lo suficientemente grande. : | Quizás D (D (D (99))) es lo suficientemente grande.
Simplemente hermoso arte
1
Si alguien quiere ayudarme aquí, el siguiente plan lógico de ataque es generar una macro para compactar "(x = ¬x)% 2! = 0" en una macro de una sola letra. No puedo entender las macros de Julia, así que alguien más podría ser útil aquí.
eaglgenes101
4

JavaScript, 190B, H ψ (ε Ω + 1 ) (9) Basado en este análisis

A=[0,1,2];B=[0,1,2];for(F=C=9;F;F--){for(C++,G=0;G<=F;G++)(A[F]||A[F-G]<A[F]-H)&&(B[F]?(I=G,G=F):(H=A[F]-A[F-G],B[F-G]<B[F]&&(I=G,G=F)));for(J=0;J<C*I;J++)A[F]=A[F-I]+H,B[F]=B[F-I],F++;H=0}C

Este programa es una versión modificada de esta traducción de números de secuencia de pares 225B en JavaScript . Para el número de secuencia de pares y su código original, consulte aquí .

Las modificaciones realizadas:

  • Está en JavaScript en lugar de BÁSICO.
  • Sin iteración (f ψ (Ω ω +1) -> f ψ (Ω ω ) )
  • La secuencia es (0,0) (1,1) (2,2), que corresponde al ordinal ψ (ε Ω + 1 ). Esto está en el ordinal de la jerarquía de Hardy
Naruyoko
fuente