Googology Wiki
Advertisement
Googology Wiki

While searching the internet, I found this document concerning busy beavers. Most of it covers things that are already known to us, but it also defines a new variant of the busy beaver: the beeping busy beaver. As of now, there are about 60,000 google results for 'beeping busy beaver' where beeping is required, but only about ten of them are relevant, so this is a very obscure concept. You should look at the document, but here is a summary (possibly misunderstood, so please see the actual definition!): define a "beep state" of a Turing machine to be a state that the machine only visits finitely many times. If M is a Turing machine, let b(M) be the time at which it visits a beep state for the last time. BBB(n) is the largest possible value of b(M) for an n-state turing machine.

The document also briefly mentions a related function called the lazy beaver function. It is defined as the smallest number such that an n-state Turing machine does not halt in that many steps.

I also found this pdf which very briefly summarizes the document I linked to prevously.

Advertisement