Busy Beavers

The most embarassing memory I have about my intellectual development as a computer scientist was the day I decided that maybe Turing got that halting problem thing wrong. I know, I know, what was a thinking! Blame it on youth. But I also blame it on a gap in my education on the theory of computation. See, I was taught about Turing Machines (TM) but was never exposed to Busy Beavers (BB) until much later.

My thinking at the time was that Turing pulled out a very contrived type of TM in his halting problem proof. He made the TM self referential to achieve the proof. So my thinking was that perhaps the only class of TM that could evade a halting detection algorithm was the class offered by Turing in his proof. I thought it was possible for the vast majority of other TM to be shown to halt algorithmically. My thinking went as follows:

1. A TM is a deterministic device.
2. If a TM goes through a sequence of states and at some point returns to a state already visited without halting then that TM will never halt. Here it is important to relaize I am including the tape in the state specification.

My "algorithm" for detecting a TM that did not halt was simply to run a TM in a simulator that at each step would save a snapshot of the entire state and compare to previous snapshots to find a duplicate. If a duplicate was found then it would declare the TM would not halt. For this to actually work the algorithm would have to set some bounds on how long it would run the simulation. I did not think this was a problem because I thought there was obviously a linear or at worst quadratic function based on the number of possible states in the input TM. And, of course, this is where I was wrong. Had I known about Busy Beavers I would not have gone down this road.

It turns out the the Busy Beaver function looks something like this for a two symbol TM:

States	Steps
1	1
2	6
3	38
4	>=3,932,964
5	>=1.9 × 10^704

Linear indeed!

The silver lining for me is that I learned a very important lesson (besides the one about not doubting a mathematical proof by someone of Turing's stature that withheld the scrutiny of thousands of individuals of similar stature). I learned that human intuition about the emergence of complexity from simple mechanisms is woefully poor. This lesson is repeated when we look at Cellular Automata in NKS. Its also repeated when we compute the number of possible configurations of a chessboard and compare that the estimates of the number of atoms in the known universe.

Luckily I learned my lessons while I was still quite young. Many individuals who believe themselves to be intellectuals have never learned to not always trust what they believe is intuitively reasonable. That not so bad except they use the web to infect the gullible with their intuitions. So, be careful out there! There are a lot of busy beavers with bad intuition.