1. 13
  1. 3

    I dunno, it seems like it should be entirely feasible to brute-force it and exact numbers for BB(n) for “small” values, at least lower than a trillion or so. So, BB(5) or BBB(4). Just generate all the possible Turing machines with that many states, then execute them each and count how many steps each one takes before it halts…


    Edit: The author’s review paper here is also well worth reading, in my case more for the commentary and philosophy than the math itself. It’s very nice to find something so interesting, so fundamentally useless, and still so insightful.

    1. 2

      The article doesn’t explain what Busy Beaver is. Of course there’s a Wikipedia page, but I’m coming around to the idea (with apologies to any algorithmic Wikipedia page authors out there) that Wikipedia is the worst place in the known universe to go if you want to actually understand a concept in computer science.

      I found this video rather helpful.

      1. 2

        This essay from the same author in 1999 is a good introduction: https://www.scottaaronson.com/writings/bignumbers.html.