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 código de golf, 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.
fuente
TREE(3)+1
allí ganoRespuestas:
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!
Ungolfed: (usando funciones, no lambdas)
OCF extendido de Madore:
Y (groseramente) la función phi de Veblen:
Explicación sin ordinales:
Mi programa inicia
k = 9, h = [[],9,9]
. Luego aplicak = k*k
yh = f(h,k)
hastah == 0
y salidask
.Explicación con ordinales:
ψ '(ω ∙ α) ≈ ψ (α), la función de colapso ordinal descrita en la imagen de arriba.
Mi programa se inicia más o menos
k = 9
yh = Ω(↑9)9
, luego, se aplicak ← k²
yh ← h[k,h]
hastah = 1
y vuelvek
.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 ψ ' 0 (Ω 9 ) (9) (ver historial de revisiones , además el nuevo es mucho mejor)
fuente
a.class!=Array
, lo más idiomático es!a.is_a? Array
pero lo más corto que se me ocurrea!=[*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.Haskell, 252 Bytes, ÁRBOL (3) +1
¡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 c
es un árbol con etiquetac
y nodosn
.c
debe ser1
,2
o3
.l t
es el número de nodos en un árbolt
.t1 # t2
es verdadero si set1
integra homeomórficamente ent2
(basado en la definición 4.4 aquí ), y falso de lo contrario.a n
saca una gran lista de árboles. La lista exacta no es importante. La propiedad importante es quea n
contiene todos los árboles hastan
nodos, con nodos están etiquetados con1
,2
, o3
, tal vez algunos árboles y más también (pero esos otros árboles también se pueden marcar con1
,2
o3
). También se garantiza la salida de una lista finita.s n
enumera todas las secuencias de longitudn
de 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.main
imprime el más pequeño den
modo que no haya secuencias válidas de longitudn
.Como
TREE(3)
se define como la longitud de la secuencia válida más larga,TREE(3)+1
es la más pequeña, den
modo que no hay secuencias válidas de longitudn
, que es lo que genera mi programa.fuente
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.
Pruébalo en línea!
Versión mejor espaciada:
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).
fuente
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í .
Pruébalo en línea!
Versión sin golf:
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).
fuente
u==0?v:u==[]?v
, podrías escribiru==0?||u[0]?v
, lo que ahorra dos bytes.Julia, 569 bytes, número del cargador
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:
No hay conteos anteriores porque hice demasiados errores de bytes en el golf agresivo que he hecho.
fuente
JavaScript, 190B, H ψ (ε Ω + 1 ) (9) Basado en este análisis
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:
fuente