A função TREE (k) fornece o comprimento da sequência mais longa de árvores T ₁ , T ₂ , ... onde cada vértice é rotulado com uma das k cores, a árvore T _i tem no máximo i vértices e nenhuma árvore é uma menor de qualquer árvore após a sequência.

ÁRVORE (1) = 1, com, por exemplo, T ₁ = (1).

ÁRVORE (2) = 3: por exemplo, o t ₁ = (1); T ₂ = (2)--(2); T ₃ = (2).

ÁRVORE (3) é um grande número grande . Ainda maior que o número de Graham. Seu trabalho é produzir um número ainda maior que ele!

Este é um código-golfe, portanto, o objetivo é escrever o programa mais curto em qualquer idioma que produza deterministicamente um número maior ou igual a TREE (3) (ao stdout).

• Você não tem permissão para receber informações.
• Seu programa deve terminar eventualmente, mas você pode assumir que a máquina possui memória infinita.
• Você pode assumir que o tipo de número do seu idioma pode conter qualquer valor finito, mas precisa explicar como isso funciona exatamente no seu idioma (por exemplo: um flutuador tem precisão infinita?)
  • Infinidades não são permitidas como saída.
  • O fluxo insuficiente de um tipo de número gera uma exceção. Não envolve.
• Como TREE (3) é um número tão complexo, você pode usar a aproximação da hierarquia de crescimento rápido f _{ϑ (Ω ^ω ω) +1} (3) como o número a ser batido.
• Você precisa fornecer uma explicação do motivo pelo qual seu número é tão grande e uma versão não-gasta do seu código para verificar se sua solução é válida (já que não há computador com memória suficiente para armazenar o TREE (3) )

Nota: Nenhuma das respostas atualmente encontradas aqui funciona.

Por que o TREE (3) é tão grande?

Ruby novo, 135 bytes, >> H _{ψ (φ 3 (Ω + 1))} (9)

onde H é a hierarquia Hardy, ψ é uma versão estendida do OCF de Madore (será explicado abaixo) e φ é a função Veblen.

Experimente online!

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 funções, não 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 estendido de Madore:

E (grosseiramente) a função phi de Veblen:

Explicação sem ordinais:

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]

Meu programa inicia k = 9, h = [[],9,9]. Em seguida, aplica-se k = k*ke h = f(h,k)até h == 0e saídas k.

Explicação com os ordinais:

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]

ψ '(ω ∙ α) ≈ ψ (α), a função de colapso ordinal descrita na imagem acima.

Meu programa inicia mais ou menos k = 9e h = Ω(↑9)9, em seguida, aplica k ← k²e h ← h[k,h]até h = 1e retorna k.

E assim, se eu fiz isso direito, [[],9,9]é muito maior que o ordinal de Bachmann-Howard ψ (Ω ^{Ω Ω ...} ), que é muito maior que ϑ (Ω ^ω ω) +1.

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

E se minha análise estiver correta, deveríamos ter ψ '(Ω ^Ω ∙ x) ~ = ψ * (Ω ^Ω ∙ x), onde ψ * é a função psi normal de Madore. Se isso acontecer, meu ordinal é aproximadamente ψ * (φ ₃ (Ω + ω)).

Old Ruby, 309 bytes, H _{ψ ' 0 (Ω 9 )} (9) (consulte o histórico de revisões , além do novo ser muito melhor)

Haskell, 252 bytes, ÁRVORE (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

Obrigado pela ajuda de H.PWiz, Laikoni e Ørjan Johansen pela ajuda no golfe!

Conforme sugerido pelo HyperNeutrino , meu programa gera TREE (3) +1, exatamente (TREE é computável como se vê).

T n cé uma árvore com rótulo ce nós n. cdeve ser 1, 2ou 3.

l té o número de nós em uma árvore t.

t1 # t2é verdadeiro se t1incorporado homeomorficamente t2(com base na definição 4.4 aqui ) e falso caso contrário.

a ngera uma grande lista de árvores. A lista exata não é importante. A propriedade importante é que a ncontém todas as árvores até nnós, com nós de ser rotulado com 1, 2, ou 3, e talvez algumas mais árvores, bem como (mas essas outras árvores também será marcado com 1, 2ou 3). Também é garantido a saída de uma lista finita.

s nlista todas as sequências de comprimento ndas árvores, de modo que o inverso (desde que a construamos para trás) dessa sequência seja válido. Uma sequência é válida se o enésimo elemento (onde começamos a contar com 1) tiver no máximo n nós e nenhuma árvore homeomorficamente se incorporar a um nó posterior.

mainimprime o menor, de nmodo que não haja seqüências válidas de comprimento n.

Como TREE(3)é definido como o comprimento da maior seqüência válida, TREE(3)+1é o menor, de nmodo que não haja sequências válidas de comprimento n, que é o que meu programa gera.

Python 2, 194 bytes, ~ H _{ψ (Ω ^{Ω Ω} )} (9)

onde H é a hierarquia de Hardy e ψ é a função de colapso ordinal abaixo do ordinal de Bachmann-Howard definido por Pohlers.

Agradecimentos a Jonathan Frech por -3 bytes.

def S (T): retorne 0 se T == 1else [S (T [0])] + T [1:]
def R (T): U = T [0]; V = T [1:]; exec "global B; B = T" * (T [-1] == 0); retornar [S (B)] + V se U == 1else [R (U)] * c + V se U mais V
A = [[[1,1], 1], 0]
c = 9
enquanto A: A = R (A); c * = c
imprimir c

Experimente online!

Versão melhor espaçada:

def S (T):
  retornar 0 se T == 1 else [S (T [0])] + T [1:]

def R (T):
  U = T [0]
  V = T [1:]
  B global
  se T [-1] == 0:
    B = T
  se U == 1: 
    retornar [S (B)] + V
  retornar [R (U)] * c + V se U mais V

A = [[[1,1], 1], 0]
c = 9
enquanto um:
  A = R (A)
  c * = c
imprimir c

Explicação:

Este programa implementa uma variante da hidra de Buchholz , usando apenas rótulos de 0 e 1. Basicamente, a cada passo, observamos o primeiro nó da folha da árvore e verificamos se está marcado com 0 ou 1.

-Se o nó folha é rotulado com 0, excluímos o nó folha e copiamos a árvore a partir do pai do nó folha c vezes, todas as cópias conectadas ao avô do nó folha.

-Se o nó folha é rotulado com 1, então pesquisamos de volta para a raiz até chegarmos a um nó ancestral rotulado com 0. Seja S a árvore que começa nesse nó ancestral. Seja S 'S com o nó da folha rotulado novamente com 0. Substitua o nó da folha por S'.

Em seguida, repetimos o processo até não termos mais nada além do nó raiz.

Este programa difere do procedimento normal da hidra de Buchholz de duas maneiras: Primeiro, depois de executar o procedimento acima, recuamos novamente na árvore e fazemos o procedimento de cópia do rótulo 0 descrito acima para cada nó ancestral do nó folha original. Como aumenta o tamanho da árvore, nosso procedimento levará mais tempo que a hidra normal de Buchholz e, portanto, levará a um número maior no final; no entanto, ele ainda será encerrado porque o ordinal associado à nova árvore ainda será menor que a árvore antiga. A outra diferença é que, em vez de começar com c = 1 e aumentar 1 a cada vez, começamos com c = 9 e o colocamos ao quadrado toda vez, porque por que não?

A árvore [[[1,1], 1], 0] corresponde ao ordinal ψ (Ω ^{Ω Ω} ), que é consideravelmente maior que o ordinal ϑ (Ω ^ω ω) e, portanto, nosso número final resultante de cerca de H _{ψ (Ω ^{Ω Ω} )} (9) excederá definitivamente a ÁRVORE (3).

Ruby, 140 bytes, ~ H _{ψ (Ω ^{Ω Ω} )} (81)

onde H é a hierarquia de Hardy e ψ é a função de recolhimento ordinal padrão abaixo do ordinal de Bachmann-Howard, conforme definido aqui .

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

Experimente online!

Versão não destruída:

def S (a)
  * v, u = a
  se a == 1 
    Retorna []
  outro
    retornar v + [S (u)]
  fim
fim  

def R (t)
  * v, u = t
  se t [0] == []
    $ b = t
  fim
  se u == 1
    retornar v + [S ($ b)]
  elsif u == []
    retornar v
  outro
    retornar v + [R (u)] * $ c
  fim
fim

$ c = 9

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

enquanto a! = [] faz
  $ c * = 9
  a = R (a)
fim

print $ c

Este programa implementa a hidra de Buchholz com nós rotulados com [] e 1, conforme descrito na minha entrada do Python 2.

A árvore [[], [1, [1,1]]] corresponde ao ordinal ψ (Ω ^{Ω Ω} ), que é consideravelmente maior que o ordinal ϑ (Ω ^ω ω) = ψ (Ω ^{Ω ω ω} ) e portanto, nosso número final resultante de cerca de H _{ψ (Ω ^{Ω Ω} )} (81) excederá ÁRVORE (3).

Julia, 569 bytes, Número do carregador

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 economizar um pouco de trabalho braçal, decidi portar o Loader.c para Julia quase um por um e compactá-lo no bloco de código acima. Para aqueles que desejam fazer as comparações eles mesmos (para verificar minha pontuação ou para me ajudar a encontrar erros ou melhorar meu código), uma versão não-gasta está abaixo:

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

Nenhuma contagem anterior porque fiz muitos erros de bytes no golfe agressivo que fiz.

JavaScript, 190B, H _{ψ (ε Ω + 1 )} (9) _{Baseado nesta análise}

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 é uma versão modificada desta tradução de número de sequência de pares 225B em JavaScript . Para o número de sequência de pares e seu código original, consulte aqui .

As modificações feitas:

• Está em JavaScript em vez de em BASIC.
• Sem iteração (f _{ψ (Ω ω +1)} -> f _{ψ (Ω ω )} )
• A sequência é (0,0) (1,1) (2,2), que corresponde ao ordinal ψ (ε _{Ω + 1} ). _{Isso está no ordinal da hierarquia Hardy}