Loader's Number(googology.fandom.com)
63 pointsby lisper12 days ago2 comments
  • tromp12 days ago
    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

    • rvnx12 days ago
      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 ?

      • knome12 days ago
        >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?

        • 10 days ago
          undefined
      • zimpenfish12 days ago
        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...
        • rvnx12 days ago
          Ok, that makes it much more interesting, I get it now. It's the "execution eventually terminates" that is tricky. Thank you!
      • throwaway8152312 days ago
        > 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.

      • tromp12 days ago
        Amazingly, this can be done in literally a bit over 6 bytes, shorter than an empty for-loop in many languages...
      • 12 days ago
        undefined
  • 12 days ago
    undefined