Busy Beavers
Computers are a wonderful invention, capable of a profound variety of actions. But there are limits to what a computer can do, and today I wish to talk about one of them. Specifically, I wish is discuss the Busy Beaver problem.
The busy beaver function, denoted here as B(x), is a function that returns the highest number of 1s a turing machine with x states can print on an initially blank tape before halting. An alternative formulation of the questions asks “How many steps can the turing machine take before halting?”. The two questions have essentially the same properties, but the later is slightly easier to reason about, so for the purpose of this discussion, we will use it as our working definition.
This function happens to be incomputable, i.e. there is no program that when carried out by a computer will calculate the value of B(x) for any x.
There are several ways of proving this to be the case, but perhaps the simplest is this.
As Turing proved, the halting problem (giving a computer and a program, determine if the computer ever stops once started executing the program) is non-computable.
If the busy beaver problem were computable, then the halting problem would be computable as well. But we already know the halting problem cannot be computed. So B(x) cannot be computed either.
How can we use B(x) to solve the halting problem? Like this: Say we have an n state turning machine and some program, and we wish to know if it halts or not when started on a blank tape. First, calculate the value B(x). This value will place an upper limit on the number of internal states the program in questions can go through. Then, run the program on the turing machine. Either the turing machine will execute a certain number of steps less than or equal to B(x) and halt, or it will execute a number of steps greater than B(x) and never halt. We keep track of the number of states the machine has gone through, and once it crosses the critical threshold at B(x), we know the machine will not halt. The limitation of working on a blank tape really is not a limitation, as any program can be re-written with all the needed variables coded into the machine.
So B(x) is uncomputable. But we can still discover information about it. For example, B(1) = 1. The machine has 1 state and starts on a blank square. So the condition the machine is in when started (in state 1, looking at a blank spot on the tape) is identical to every state the machine can ever be in. So it either halts immediately (i.e. 1 step) or it never does.
Below are all the possible configurations of this single state.
Tape Symbol Write Symbol Move Head Next state
0 1 Left 1
0 1 Left Halt
0 1 Right 1
0 1 Right Halt
0 0 Left 1
0 0 Left Halt
0 0 Right 1
0 0 Right Halt
1 1 Left 1
1 1 Left Halt
1 1 Right 1
1 1 Right Halt
1 0 Left 1
1 0 Left Halt
1 0 Right 1
1 0 Right Halt
There are 16 ways the single state can be arranged. In our formulation of the problem, we are considering a machine acting on a blank tape, so all configurations that consider a square with a 1 in it are thrown out immediately, leaving us with 8 possible states. Of these 8, 4 of them write a 0 (or blank) on the tape, so these are thrown out as well, leaving us 4. Of these 4, two of them write a 1, move one square left or right and halt, and two of them write a 1, move one square left or right, and go back into state 1. It is obvious that the latter machines must never halt. They go into an infinite loop, wherein they are considering a blank square, write a 1 on that square move left/right, and repeat, forever. It is also obvious that the former machines will only print a single 1 before halting.
So from this exhaustive examination of 1 state machines, we can conclude that B(1) = 1. We can also conclude (indeed, we just showed this in the preceding paragraph) that a single state machine will either execute one instruction or halt, or execute an infinite number of instructions and never halt.
Present knowledge about the value of B(x) looks something like this:
n B(n)
1 1
2 4
4 13
5 >=4098
A curious property of B(x), and part of the reason it is uncomputable, is that f(B(x)) is smaller than B(x+1) for infinitely many x. The function B(x) grows at a truly astronomical rate. In fact, it grows faster than any computable function, and is therefore not one of the set of computable functions.
Put more precisely, for any computable function f, B(x + 1) > f(B(x)) for infinitely many x. For example, if f were x^10,000, then B(x + 1) > x^10,000 for infinitely many x. Since this holds for all computable function, it follows that the output of B(x) is not identical to the output of any particular computable function, and hence B(x) is not itself a computable function.