45
\$\begingroup\$

The function TREE(k) gives the length of the longest sequence of trees T1, T2, ... where each vertex is labelled with one of k colours, the tree Ti 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. T1 = (1).

TREE(2) = 3: e.g. T1 = (1); T2 = (2)--(2); T3 = (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 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?

\$\endgroup\$
  • 9
    \$\begingroup\$ @StepHen not trivally. Getting to Tree(3) requires a whole new paradigm. \$\endgroup\$ – PyRulez Aug 16 '17 at 18:58
  • 1
    \$\begingroup\$ relevant: codegolf.meta.stackexchange.com/questions/14057/… \$\endgroup\$ – fejfo Oct 14 '17 at 6:08
  • 11
    \$\begingroup\$ TREE(3)+1 there I win \$\endgroup\$ – HyperNeutrino Oct 14 '17 at 23:44
  • 1
    \$\begingroup\$ @KSmarts You do realize none of the answers there come close to TREE(3)? \$\endgroup\$ – Simply Beautiful Art Oct 19 '17 at 23:53
  • 2
    \$\begingroup\$ @MDXF I'm gonna say no, because using INT_MAX is kinda a cheating (otherwise, print INT_MAX would insta win). In general, your output needs to be the same for any sufficiently large system. \$\endgroup\$ – PyRulez Oct 26 '17 at 7:30
37
\$\begingroup\$

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:

enter image description here

And (crudely) Veblen's phi function:

enter image description here

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 ψ*(φ3(Ω+ω)).


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

\$\endgroup\$
  • \$\begingroup\$ I could only test my program for very few values, so do excuse me if I've made a mistake somewhere. \$\endgroup\$ – Simply Beautiful Art Oct 20 '17 at 20:19
  • \$\begingroup\$ Bleh, slowly but surely trying to think my way through and fixing anything I see wrong. :-( So tedious. \$\endgroup\$ – Simply Beautiful Art Oct 20 '17 at 22:26
  • \$\begingroup\$ Hmm... so $f_{ψ_0(ψ9(9))}(9)$ means we need at least the $ψ_9(9)$ th weakly inaccessible cardinal level of the fast growing hierarchy with base 9 to get larger than $TREE(3)$ \$\endgroup\$ – Secret Oct 21 '17 at 8:54
  • 1
    \$\begingroup\$ Golf nitpicks: You can definitely golf a.class!=Array, most idiomatic is !a.is_a? Array but shortest I can think of is a!=[*a]. And the methods can be converted into lambdas: f=->a,n=0,b=a{...}...f[x,y] to save some characters and maybe open up refactoring possibilities using them as first-class objects. \$\endgroup\$ – histocrat Oct 24 '17 at 16:05
  • 1
    \$\begingroup\$ @PyRulez D= Guess I'll get working on some super golfing ordinals then. \$\endgroup\$ – Simply Beautiful Art Oct 28 '17 at 1:20
22
\$\begingroup\$

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.

\$\endgroup\$
15
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Not so golfy my friend :-) \$\endgroup\$ – Simply Beautiful Art Oct 25 '17 at 11:53
  • \$\begingroup\$ I know. I don't know how to reduce it further, at least not in Python. Maybe I can try to learn some Ruby. \$\endgroup\$ – Deedlit Oct 25 '17 at 12:05
  • \$\begingroup\$ Is it possible to put R(T) all on one line? \$\endgroup\$ – Simply Beautiful Art Oct 25 '17 at 20:47
  • \$\begingroup\$ @SimplyBeautifulArt Most likely yes (TIO link), though untested. \$\endgroup\$ – Jonathan Frech Oct 27 '17 at 14:57
  • \$\begingroup\$ @JonathanFrech Thanks for your help! Unfortunately, when I tried your code it gave an error message "global B is not defined". I have no idea why this gives an error while the original code does not, so I don't know how to fix it. \$\endgroup\$ – Deedlit Oct 31 '17 at 3:40
6
+50
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Dang it you and your 149 bytes. \$\endgroup\$ – Simply Beautiful Art Nov 1 '17 at 22:59
  • \$\begingroup\$ But Ruby for the win :P \$\endgroup\$ – Simply Beautiful Art Nov 1 '17 at 23:04
  • \$\begingroup\$ Golf nitpick: Rather than writing u==0?v:u==[]?v you could write u==0?||u[0]?v, which saves two bytes. \$\endgroup\$ – Simply Beautiful Art Nov 7 '17 at 11:43
  • \$\begingroup\$ @SimplyBeautifulArt Thanks for the help! Balls back in your court. :D \$\endgroup\$ – Deedlit Nov 7 '17 at 13:11
  • 2
    \$\begingroup\$ D:< that 1 byte difference between us is the most frustrating thing ever. \$\endgroup\$ – Simply Beautiful Art Nov 9 '17 at 12:24
6
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Oh dear. 1 more addition to this madness of a place. \$\endgroup\$ – Simply Beautiful Art Nov 10 '17 at 2:09
  • 1
    \$\begingroup\$ Also, while I've no proof of this, I think that D(D(D(D(99)))) is large enough. :| Maybe D(D(D(99))) is large enough. \$\endgroup\$ – Simply Beautiful Art Nov 10 '17 at 2:11
  • 1
    \$\begingroup\$ If anyone wants to help me here, the next logical plan of attack is to generate a macro to compact "(x=¬x)%2!=0" into a single-letter macro. Can't figure out Julia macros myself, so someone else could be of use here. \$\endgroup\$ – eaglgenes101 Dec 4 '17 at 3:32
4
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.