Golf a number bigger than TREE(3)

Question

The function TREE(k) gives the length of the longest sequence of trees T₁, T₂, ... where each vertex is labelled with one of k colours, the tree T_i has at most i vertices, and no tree is a minor of any tree following it in the sequence.

TREE(1) = 1, with e.g. T₁ = (1).

TREE(2) = 3: e.g. T₁ = (1); T₂ = (2)--(2); T₃ = (2).

TREE(3) is a big big number. Even bigger than Graham's number. Your job is to output a number even bigger than it!

This is a code-golf so the goal is to write the shortest program in any language that deterministically outputs a number bigger than or equal to TREE(3) (to the stdout).

• You aren't allowed to take input.
• Your program must eventually terminate but you can assume the machine has infinite memory.
• You might assume your language's number type can hold any finite value but need to explain how this exactly works in your language (ex: does a float have infinite precision?)
  • Infinities are not allowed as output.
  • Underflow of a number type throws an exception. It does not wrap around.
• Because TREE(3) is such a complex number you can use the fast growing hierarchy approximation f_{ϑ(Ω^ω ω)+1}(3) as the number to beat.
• You need to provide an explanation of why your number is so big and an ungolfed version of your code to check if your solution is valid (since there is no computer with enough memory to store TREE(3))

Note: None of the answers currently found here work.

Why is TREE(3) so big?

Answer 1

New Ruby, 135 bytes, >> H_{ψ(φ3(Ω+1))}(9)

where H is the Hardy hierarchy, ψ is an extended version of Madore's OCF (will explain below) and φ is the Veblen function.

Try it 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: (using functions, not 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

Madore's extended OCF:

And (crudely) Veblen's phi function:

Explanation without ordinals:

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]

My program initiates k = 9, h = [[],9,9]. It then applies k = k*k and h = f(h,k) until h == 0 and outputs k.

Explanation with ordinals:

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]

ψ'(ω∙α) ≈ ψ(α), the ordinal collapsing function described in the image above.

My program more or less initiates k = 9 and h = Ω(↑9)9, then applies k ← k² and h ← h[k,h] until h = 1 and returns k.

And so if I did this right, [[],9,9] is way bigger than the Bachmann-Howard ordinal ψ(Ω^ΩΩ...), which is way bigger than ϑ(Ω^ωω)+1.

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

And if my analysis is correct, then we should have ψ'(Ω^Ω∙x) ~= ψ*(Ω^Ω∙x), where ψ* is the normal Madore's psi function. If this holds, then my ordinal is approximately ψ*(φ₃(Ω+ω)).

---

Old Ruby, 309 bytes, H_ψ'0(Ω9)(9) (see revision history, besides the new one is way better)

Answer 2

Haskell, 252 Bytes, TREE(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

Thanks for help from H.PWiz, Laikoni and Ørjan Johansen for help golfing the code!

As suggested by HyperNeutrino, my program outputs TREE(3)+1, exactly (TREE is computable as it turns out).

T n c is a tree with label c and nodes n. c should be 1, 2, or 3.

l t is the number of nodes in a tree t.

t1 # t2 is true if t1 homeomorphically embeds into t2 (based on Definition 4.4 here), and false otherwise.

a n outputs a big list of trees. The exact list isn't important. The important property is that a n contains every tree up to n nodes, with nodes being labelled with 1, 2, or 3, and maybe some more trees as well (but those other trees will also be labelled with 1, 2, or 3). It is also guaranteed to output a finite list.

s n lists all sequences length n of trees, such that the reverse (since we build it backwards) of that sequence is valid. A sequence is valid if the nth element (where we start counting at 1) has at most n nodes, and no tree homeomorphically embeds into a later one.

main prints out the smallest n such that there is no valid sequences of length n.

Since TREE(3) is defined as the length of the longest valid sequence, TREE(3)+1 is the smallest n such that there are no valid sequences of length n, which is what my program outputs.

Answer 3

Python 2, 194 bytes, ~ H_ψ(Ω^ΩΩ)(9)

where H is the Hardy hierarchy, and ψ is the ordinal collapsing function below the Bachmann-Howard ordinal defined by Pohlers.

Thanks to Jonathan Frech for -3 bytes.

def S(T):return 0if T==1else[S(T[0])]+T[1:]
def R(T):U=T[0];V=T[1:];exec"global B;B=T"*(T[-1]==0);return[S(B)]+V if U==1else[R(U)]*c+V if U else V
A=[[[1,1],1],0]
c=9
while A:A=R(A);c*=c
print c

Try it online!

Better spaced version:

def S(T):
  return 0 if T==1 else [S(T[0])]+T[1:]

def R(T):
  U=T[0]
  V=T[1:]
  global B
  if T[-1]==0:
    B=T
  if U==1: 
    return [S(B)]+V
  return [R(U)]*c+V if U else V

A=[[[1,1],1],0]
c=9
while A:
  A=R(A)
  c*=c
print c

Explanation:

This program implements a variant of the Buchholz hydra, using just labels of 0 and 1. Basically, at each step, we look at the first leaf node of the tree, and see if it is labelled with a 0 or a 1.

-If the leaf node is labelled with a 0, then we delete the leaf node, and then copy the tree starting from the parent of the leaf node c times, all of the copies connected to the grandparent of the leaf node.

-If the leaf node is labelled with a 1, then we search back towards the root until we reach an ancestor node labelled with a 0. Let S be the tree starting from that ancestor node. Let S' be S with the leaf node relabelled with 0. Replace the leaf node with S'.

We then repeat the process until we have nothing left but the root node.

This program differs from the normal Buchholz hydra procedure in two ways: First, after we do the above procedure, we recurse back up the tree, and do the label 0 copy procedure described above for each ancestor node of the original leaf node. This increases the size of the tree, so our procedure will take longer than the normal Buchholz hydra, and therefore lead to a bigger number in the end; however, it will still terminate because the ordinal associated with the new tree will still be less the the old tree. The other difference is, rather than start with c = 1 and increasing 1 each time, we start with c = 9 and square it each time, because why not.

The tree [[[1,1],1],0] corresponds to the ordinal ψ(Ω^ΩΩ), which is considerably bigger than the ordinal ϑ(Ω^ωω), and so our resulting final number of about H_ψ(Ω^ΩΩ)(9) will definitely exceed TREE(3).

Answer 4

Ruby, 140 bytes, ~ H_ψ(Ω^ΩΩ)(81)

where H is the Hardy hierarchy, and ψ is the standard ordinal collapsing function below the Bachmann-Howard ordinal, as defined here.

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

Try it online!

Ungolfed version:

def S(a)
  *v, u = a
  if a == 1 
    return []
  else
    return v + [S(u)]
  end
end  

def R(t)
  *v, u = t
  if t[0] == []
    $b = t
  end
  if u == 1
    return v + [S($b)]
  elsif u == []
    return v
  else
    return v + [R(u)]*$c
  end
end

$c = 9

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

while a != [] do
  $c *= 9
  a = R(a)
end

print $c

This program implements the Buchholz hydra with nodes labelled with []'s and 1's, as described in my Python 2 entry.

The tree [[],[1,[1,1]]] corresponds to the ordinal ψ(Ω^ΩΩ), which is considerably bigger than the ordinal ϑ(Ω^ωω) = ψ(Ω^Ωωω), and so our resulting final number of about H_ψ(Ω^ΩΩ)(81) will exceed TREE(3).

Answer 5

Julia, 569 bytes, Loader's Number

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

To save myself a bit of legwork, I decided to port Loader.c to Julia nearly one-for-one and compact it into the block of code above. For those that want to do the comparisons themselves (either to verify my scoring or to help me find mistakes or improve my code), an ungolfed version is below:

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 previous counts because I made way too many byte miscounts in the aggressive golfing I've done.

Answer 6

JavaScript, 190B, H_ψ(εΩ+1)(9)_{Based off of this analysis}

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

This program is a modified version of this 225B Pair-sequence number translation in JavaScript. For Pair-sequence number and their original code, see here.

The modifications done:

• It is in JavaScript instead of BASIC.
• No iteration(f_ψ(Ωω+1)->f_ψ(Ωω))
• The sequence is (0,0)(1,1)(2,2), which corresponds to ordinal ψ(ε_Ω+1)._{This is in Hardy-hierarchy ordinal}