For Scott Aaronson
In Syracuse, in Sicily, third century BC
The brilliant Archimedes boasted in a book that he
Had written down a number so enormous and so grand
That even if the universe were filled with grains of sand
The number he has written down, he lucidly explains,
Exceeds by far the number of that universe of grains.
The man who claimed he'd move the Earth if he could get a lever
Would have been thrilled to learn about the function Busy Beaver.
The Busy Beaver function was defined in '62.
It's easy to define, as I will demonstrate to you.
Get each machine of Turing with states exactly n,
And give them each an empty tape to work upon; and when
The last one that is going to stop has reached its halting state
And all the rest will never halt, however long you wait,
Then note the time that has elapsed, for that is going to be
The value of BB(n) computed flawlessly,
The function starts out slowly. In fact BB(1)
is 1 --- the proof is trivial; it isn't any fun.
BB(2) is 6 and 21 is BB-3.
The proof of those were part of Shen Lin's doctoral degree.
BB(4) is 107 (Brady, '83).
The Busy Beaver Challenge Team in 2024
Proved BB-5 is forty-seven million -- slightly more.
BB(6) is quite an unimaginable beast.
A stack of 15 10's stacked exponentially, at least!
They've also proved that we cannot, however hard we strive,
Compute the value of BB(745).
But speaking realistically, I doubt that we'll ever see
Another exact value of the function of BB.
This is part of the collection Verses for the Information Age by Ernest Davis
To fit the the meter, "BB(n)" should be read "bee bee of en". Likewise
"BB(1)" etc.
"BB-3" and "BB-5" should be read "bee bee three" and "bee bee five".
"107" should be read "one-oh-seven".
"2024" should be read "twenty twenty-four".
"BB(745)" should be read "bee bee of seven forty-five"