2025-06-11
The busy beaver function, BB(n), gives the maximum number of 1's that can be written to the tape of a halting Turing machine with n instruction cards.
BB(n) is famous for being an incredibly fast growing function. In fact, it grows faster than any computable function. I didn't really put much thought into why this is until recently.
Without writing a proper proof, since that would be well beyond me for something like this, here is how I justify it to myself.
According to the Church-Turing thesis, we can convert any computable function into a set of instruction cards. So, given some function f(n) there must be a number of cards 𝓍 that can encode f(n) plus 1. Thus BB(𝓍) is at least as big as f(𝓍) plus 1.
The problem is there's one part of f(n) which continues growing, which is n itself. Our Turing machine needs to be able to encode the input. So we would need to show that the number of extra cards needed to encode n grows slowly enough that there's a point we can encode f(n) plus 1 and n itself within n cards.