As a follow up to Shortest terminating program whose output size exceeds Graham's number and Golf a number bigger than TREE(3), I present a new challenge.

Loader's number is a very large number, that is kind of hard to explain (since it was itself the result of a code golfing exercise with a flexible goal). There is a definition and explanation here, but for the purposes of self-containment, I will attempt to explain it later in this post as well.

The algorithm Ralph Loader used produces one of the largest numbers of any (computable) algorithm ever written! Indeed, Loader's number is the largest "computable" number on the Googology Wiki. (By "computable" number, they mean a number defined in terms of a computation.) That means that if answer produces a number larger than Loader's number in an interesting way (i.e. not just Loader's number+1), you could go down in Googology history! That being said, programs that produce something like Loader's number+1 are definitely valid answers and contenders to this question; just don't expect any fame.

Your job is to create a terminating program that produces a number larger than Loader's number. This is , so the shortest program wins!

  • You aren't allowed to take input.
  • Your program must eventually terminate deterministically but you can assume the machine has infinite memory.
  • You may 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.
  • 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 Loader's number).

So here is an explanation of Loader's number. See http://googology.wikia.com/wiki/Loader%27s_number and the links therein for more precise details. In particular, it contains a program that produces Loader's number exactly (by definition).

The calculus of constructions is essentially a programming language with very particular properties.

First of all, every syntactically valid program terminates. There are no infinite loops. This will be very useful, because it means that if we run an arbitrary calculus of constructions program, our program will not get stuck. The problem is that this implies the calculus of constructions is not Turing complete.

Second of all, among non-Turing complete languages, it is one of the most powerful. Essentially, if you can prove that a Turing machine will halt on every input, you can program a function in the calculus of constructions that will simulate it. (This does not make it turing complete, because there are halting turing machines that you can not prove are halting.)

Loader's number is essentially a busy beaver number for the calculus of constructions, which is possible to compute since all coc programs terminate.

In particular, loader.c defines a function called D. Approximately, D(x) iterates over all bit-strings less than x, interprets them as a coc programs, runs the syntactically valid ones, and concatenates the results (which will also be bitstrings). It returns this concatenation.

Loader's number is D(D(D(D(D(99))))).

A more readable copy of the code from the googolology wiki

int r, a;

P(y,x){return y- ~y<<x;}

Z(x){return r = x % 2 ? 0 : 1 + Z (x / 2 );}

L(x){return x/2 >> Z(x);}

S(v,y,c,t){
   int f = L(t);         
   int x = r;
   return f-2 ? f>2 ? f-v ? t-(f>v)*c : y : P(f,P(S(v,y,c,L(x)), S(v+2,t=S(4,13,-4,y),c,Z(x)))) : A(S(v,y,c,L(x)),S(v,y,c,Z(x)));
}

A(y,x){return L(y)-1 ? 5<<P(y,x) : S(4,x,4,Z(r));}

D(x) 
{
   int f;
   int d;
   int c=0;
   int t=7;
   int u=14;
   while(x&&D(x-1),(x/=2)%2&&(1)){
      d = L(L(D(x))),
      f = L(r),
      x = L(r),
      c - r||(L(u)||L(r)-f||(x/=2)%2&&(u=S(4,d,4, r),t=A(t,d)),f/2&(x/=2)%2&&(c=P(d,c),t=S(4,13,-4,t),u=S(4,13,-4,u))),
      c&&(x/=2)%2&&(t=P(~u&2|(x/=2)%2&&(u=1<<P(L(c),u)),P(L(c),t)),c=r)
      u/2&(x/=2)%2&&(c=P(t,c),u=S(4,13,-4,t),t=9);
    }
    return a = P( P( t, P( u, P( x, c)) ),a);
}

main(){return D(D(D(D(D(99)))));}
  • You know Googology Wiki? I'm MilkyWay90 there! – MilkyWay90 Dec 3 at 23:39
  • @MilkyWay90 oh, cool. – PyRulez Dec 3 at 23:57
  • 4
    I would advise against downvoting this for similarity to the TREE(3) question: Loader's number is so much larger than TREE(3) that new and interesting approaches are required. – lirtosiast Dec 4 at 1:00
  • @Spitemaster Why do you say that? Since this is code-golf, you need to beat the other answers to be competitive. So if someone else posts a 512 byte answer, you have to beat 512 bytes to win. It's not just whoever posts an answer first. (Also, for the sake of pendantory, the original program is not valid, since answers need to produce a number larger than Loader's number.) – PyRulez Dec 4 at 1:16
  • @Spitemaster Some people also participate in languages simply to try and get the minimum possible for that language – fəˈnɛtɪk Dec 4 at 2:56

Here's a second attempt in Javascript, again based on the Buchholz hydra.

Golfed, Javascript, 624 bytes:

n=0
g=(a,h,r)=>{n++
a.forEach((A,I)=>{if(I>0){r.unshift(a)
g(a[I],h,r)
r.shift()}if(a.length==1){if(A!=0){if(A<0){a[0]=n+1
x(h)
a[0]=-1}else{t=A
k=r.filter(R=>R[0]>=0&&R[0]<A-1)[0]
if(!k){P(r,h)
return}a[I]=0
T=k[0]
k[0]=t-1
p(k).forEach((K,i)=>a[i]=K)
k[0]=T
x(h)
while(a.pop()>-3){}a[I]=t}}else P(r,h)}})}P=(r,h)=>{r[0].pop()
for(i=0;r[1]&&i<n;i++){r[1].push(p(r[0]))}x(h)
for(i=0;r[1]&&i<n;i++){r[1].pop()}r[0].push([0])}p=a=>JSON.parse(JSON.stringify(a))
x=a=>z.push(p(a))
function f(a){while(a[0]){z=[]
a.forEach(A=>g(A,A,[]))
a=p(z).filter(A=>A[1])}return n}F=a=>f(eval`[0${',[-1'.repeat(a)}${']'.repeat(a)}]`)
F(F(9))

Ungolfed:

// Counter
n=0

// Find leaves
//      a is the current node we're searching.
//      h is the base hydra.
//      r is the route back down the hydra
g=(a,h,r)=>{
    n++
    a.forEach((A,I)=>{
        // The first index is the value of the node.
        if(I>0){
            r.unshift(a)
            g(a[I],h,r)
            r.shift()
        }
        if(a.length==1){
            if(A!=0){
                if(A<0){
                    // If the node we're looking at is labelled ω, rename it
                    a[0]=n+1
                    x(h)
                    // Undo that change so it isn't propagated
                    a[0]=-1
                }else{
                    // If the node we're looking at is positive, do a fancy transformation.
                    t=A
                    k=r.filter(R=>R[0]>=0&&R[0]<A-1)[0]
                    if(!k){
                        P(r,h)
                        return
                    }
                    a[I]=0
                    T=k[0]
                    k[0]=t-1
                    p(k).forEach((K,i)=>a[i]=K)
                    k[0]=T
                    x(h)
                    // Undo the changes
                    while(a.pop()>-3){}
                    a[I]=t
                }
            }else P(r,h)
        }
    })
}

// Pop the node
P=(r,h)=>{
    // If the node we're looking at is zero, make more heads.
    r[0].pop()
    for(i=0;r[1]&&i<n;i++){
        r[1].push(p(r[0]))
    }
    x(h)
    // Undo those changes
    for(i=0;r[1]&&i<n;i++){
        r[1].pop()
    }
    r[0].push([0])
}

// Deep clone
p=a=>JSON.parse(JSON.stringify(a))

// Push
x=a=>z.push(p(a))

// Main function
function f(a){
    let count = 0;
    while(a[0]){
        // z is the next generation's hydra
        z=[]
        a.forEach(A=>g(A,A,[]))
        a=p(z).filter(A=>A[1])
    }
    return n
}

F=a=>f(eval`[0${',[-1'.repeat(a)}${']'.repeat(a)}]`)
F(F(9))

I know I have some work to do to bring the bytecount down.

This is based on the Buchholz hydra, so it's likely in roughly the same range as Loader's number. However, instead of computing the value of BH, it has a single counter for \$n\$ and then attempts every possible strategy on the hydra (in terms of order of the leafs chosen).

This is interesting because though a breadth-first search does finish because the sequence of \$n\$s for any given hydra are bounded above by \$n^n\$, it's not clear that doing a depth-first search would ever finish. This is because the starting value on the second hydra would be larger than the final value of the first hydra, and the process would (likely) go on infinitely. If someone proved that any ascending chain of strategies \$S_i\$ (where \$S_i<S_j\iff S_i(a)<S_j(a)\forall a\in S_i\$, any strategy of picking leaf nodes would finish every hydra, we'd have an even stronger function, trivially obtainable from this one.

For this reason, it feels like it's (meaningfully) stronger than the Buchholz hydra, but I'm honestly not certain.

I don't know if this beats Loader's number, though I think it's similar in magnitude. It's also too long, and I need to fix that. But I spent too long on this problem not to post something. It's also not really competitive, as it's over 512 bytes (though it might be possible to get it down).

  • You probably don't need to try every strategy. Any strategy will do. – PyRulez Dec 9 at 5:11
  • Attempting only one strategy is unlikely to beat Loader's number, as that's approximately BH. – Spitemaster Dec 9 at 13:31

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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