Busy Beaver-type functions (counting how long a program runs, provided that it terminates) might look like a mere curiosity, but they make interesting statements about the power of different systems of computation. For Turing machines it grows quicker than any computable function – and Turing machines are quite powerful!<p>If you consider a finite-state automaton, you might define a similar problem: What is the longest word that automaton accepts, provided that it accepts only finitely many words? This you can answer directly: it is n-1, where n is the number of states. And finite-state automata are not very powerful.<p>Here is another system: I give you a list of transactions, where each transaction consists of multiple instructions of the form “add/remove x units from account y”. You may only execute a transaction if no account goes negative. Here, a Busy Beaver-type question would be “What is the longest sequence of transactions that move one unit from the first account to the second, where all the others must start and end empty?” This is actually a somewhat powerful system, and here the answer grows at the rate of the Ackermann function – extremely fast (and, if you have never heard of it, probably faster than any computable function you can think of), but still computable. [1]<p>Recently we have shown a Busy Beaver-type result for a certain distributed computation model, where many (very limited) participants interact to compute things as a group. There the question was about counting how large the group is, but each participant can only count to n. So given a protocol that reliably recognises certain group sizes, what is the largest size it accepts? (Again, provided that it accepts only finitely many.) We proved that it is at most 2^(2^(2^n)) – so in some sense that model is very weak, but nevertheless much more powerful that finite state automata.<p>[1] I did not think to carefully about this, some details might be wrong.