Second thoughts on Turing Machines and Busy Beavers

Youtube comments on textbook standard BusyBeaver function introduction https://www.youtube.com/watch?v=kmAc1nDizu0 :

Fun fact: there is a finite number of states in the observable universe. You can estimate an upper bound of the number of states of a system as e^S, where S is the entropy of a black hole with the same size as the system. For our universe this ends up being around S=10^123. This means that we could only ever hope to compute up to BusyBeaver(e^10^123), as later busy beaver numbers need computations that our universe is too small to contain.

---

The op proposes to calculate BusyBeaver(e^10^123), so e^10^123 is the number of states of the Turing machine.  Therefore, the entire Universe is used to encode the Turing machine.  The tape is not accounted for.   This is somewhat of a moot point, however, since the tape of a Turing machine is (by definition) supposed to be infinite, so the real Universe couldn't accommodate a Turing machine anyway.

---

As a corollary it means our universe can only make "real" Turing machines up to k states, where BusyBeaver(k) < e^10^123.  If you try to make a Turing machine with k > 1, it will run out of tape for some configurations :) It looks like k is ... 5?

The first two comments are from strangers, but the last one is from me. Pretty sober to realize that Turing Machines with states less than the number of your fingers are not generally physically possible. It really puts a limit on the kinds of infinities we are supposed to imagine in math.

The Turing Machine and Halting Problem really hammer home two things:

- Computation irreducibility, and

- The hardness of differentiating between infinity and very large numbers

In fact, it seems that the busy beavers imply there's actually no difference unless you believe in some omnipotent God, because it's proven that you can't tell the difference once the numbers get sufficiently large.

We know that BB(745) = "infinity" (for integers at least).  So if there's any property of numbers where finite values and infinity have different qualitative properties... the transition is between 0 and BB(745). Or we just hallucinated the properties of infinity.  I tend to believe the latter is true, but maybe numbers become more surreal when they get *really* large.

Btw. Funny thing while looking up info on the subject. So this Adam Yedidia guy is a student of Scott Aaronson and was the first person to prove that BB(k) is independent of ZF for some k, and as I put his name onto Google... LOL