Loader's Number
13 comments
·April 5, 2025tromp
rvnx
In that thread, I see for example, another challenge linked on that page:
> Write the shortest possible program (length measured in bytes) satisfying the following requirements:
> infinite memory and runtime
> no input
> output is to stdout
> execution eventually terminates
> total number of output bytes exceeds Graham's number
This sounds like a loop and that's it ?
I'm struggling to see the challenge or discovery there ?
knome
>it is so large that the observable universe is far too small to contain an ordinary digital representation of Graham's number, assuming that each digit occupies one Planck volume, possibly the smallest measurable space. But even the number of digits in this digital representation of Graham's number would itself be a number so large that its digital representation cannot be represented in the observable universe. Nor even can the number of digits of that number—and so forth, for a number of times far exceeding the total number of Planck volumes in the observable universe
How do you write the halt condition for your loop in the minimal number of bytes?
zimpenfish
Given (from what I remember from Numberphile) you can't write Graham's number down in the observable universe, how are you going to make sure that the loop terminates after outputting Graham's number of bytes? Because you definitely can't put `if count > G` in there...
rvnx
Ok, that makes it much more interesting, I get it now. It's the "execution eventually terminates" that is tricky. Thank you!
throwaway81523
> This sounds like a loop and that's it ?
No, the execution is required to eventually terminate. The challenge is to find the shortest possible program that generates at least G bytes of output and then stops, where G is Graham's (extremely large) number. This is sort of like the Busy Beaver problem.
tromp
Both Graham's Number and Loader's Number appear as lower bounds in the functional Busy Beaver at https://oeis.org/A333479
tromp
Amazingly, this can be done in literally a bit over 6 bytes, shorter than an empty for-loop in many languages...
HumanOstrich
Can you provide any examples?
null
null
Last year I ported Loader's construction to Haskell [2] in order to better understand it, and managed to shrink the code down to under 232 bytes [1]. That work was also featured in a video that youtuber CodeParade made about the Quest To Find The Largest Number and its followup [3].
[1] https://github.com/tromp/AIT/blob/master/fast_growing_and_co...
[2] https://codegolf.stackexchange.com/questions/176966/golf-a-n...
[3] https://www.youtube.com/watch?v=kQLcoSuMKHg&t=10s