Why Busy Beaver Hunters Fear the Antihydra
67 points by hwayne
67 points by hwayne
Apart from the topic itself being wonderfully purposeless poking-at-the-universe-just-because, the article's art is absolutely delightful.
It's insane that the BB(5) TM halts after only 15 iterations when written as a simple loop. The explanation I guess is that a TM can only count in unary. But it does show that even a TM that saturates the BB bounds can encode a very simple algorithm.
I think it's reasonably fair to describe the goal of a BB-champion as "compute a thing as inefficiently as possible". It's not particularly surprising as a result that when trying to compute the thing efficiently it's much faster.
Certainly Turing machines of BB(5)’s level of complexity can only count in unary, but they can use binary if they are allowed more kinds of symbols on the tape.
We were given a challenge at university to make a Turing machine to calculate a base 2 integer logarithm, which is equivalent to counting the length of the input in binary. Not too hard if you have free choice of delimiter symbols, and amusingly it works for input and output in unary or binary with only the slightest tweak.
I guess if the tape is restricted to on/off then you could use extra states to implement something like Manchester coding to represent binary with delimiters, which would make arithmetic asymptotically faster.
Wow, a math article where I understood the math! Unbelievable. 😆
Thank you for this. I remember spending a while enamored with the Busy Beaver hunt as an undergrad, a long time ago. Probably courtesy of SciAm columns by Martin Gardner or Douglas Hofstadter. Somehow I'd entirely missed that BB(5) was proven. Delightful all around.
There's a lot of links to it in the article, but if you skipped over them, I suggest checking out the wiki too. It reeks of cozy nerd vibes, where you can understand half the sentence and the other half made up of English-sounding words is helpfully linked to other articles, leading to quite the rabbit hole.