Busy Beaver - Proof for BB(2) = 4

Question

Hi,

I need to prove the above claim. I can show that $BB(2)\ge 4$ by building a turing machine, but how can i show that $BB(2) \le 4$?

Searched a lot over the web, and saw that Rado proved it in 1963.

Thanks.

Answer 1

I imagine the seminar exercise went something like this.

Let $M$ be a winning machine with starting state $A$, halting state $H$ and one other state $B$. Let's build the transition function of $M$ (or an equivalent or better winner) by looking at the first few transitions. We can assume the first transition is:

$(A, 0) \mapsto (1, R, B)$

because, (a) if $M$ does not write 1, we can swap $A$ and $B$ to get a slightly faster winner, (b) if $M$ moves left, then the machine obtained from $M$ by swapping $L$ and $R$ is an equivalent winner, (c) if $M$ stays in state $A$ it will not terminate, and (d) if $M$ halts it isn't a winner.

Then we can assume the second transition is:

$(B, 0) \mapsto (t_1, L, s_1)$

for some $t_1 \in \{0, 1\}$ and $s_1 \in \{A, B\}$, because if $M$ moves right again into either state $A$ or $B$ it will not terminate and if it halts it isn't a winner.

On the third transition, we are in state $s_1$ reading 1 and we can't win by halting, so we have:

$(s_1, 1) \mapsto (t_2, d, s)$

for some $t_2 \in \{0, 1\}$, $d \in \{L, R\}$ and $s \in \{A, B\}$. As $M$ must halt, for $s_1 \not= s_2 \in \{A, B\}$, $M$ must halt on $(s_2, 1)$, so the remaining element of the transition function is:

$(s_2, 1) \mapsto (1, X, H)$

where $X$ is irrelevant and $M$ must write 1, since changing a 1 to a 0 on the last step is clearly a losing strategy. There are now just 32 possibilities for $t_1$, $t_2$, $d$, $s$ and $s_1$ to work through. I originally stopped here with an ellipsis, since in the seminar context the participants could divide the work up and do it by brute force, but let me give an argument that while still rather bitty can be checked by an individual.

After the third transition the tape looks like this:

$\begin{array}{lccccc} \mbox{Index:} & \ldots & -1 & 0 & 1 & 2 & \ldots\\ \mbox{Contents:} & \ldots & 0 & t_2 & t_1 & 0 & \ldots \end{array} $

and we are in state $s$ reading either cell $-1$ (if $d = L$) or cell $1$ (if $d = R$). I claim that $d = L$. To see this assume for a contradiction that $d = R$. Then if $t_1 = 0$, $M$ will not terminate (if $s = A$, we are essentially back in the starting position and $M$ will diverge to the right; if $s = B$ and $t_2 = 1$ $M$ will spin on cells 0 and 1 and if $s = B$ and $t_2 = 0$, $M$ will diverge to the left.) Now if $t_1 = 1$ and $s = s_2$, $M$ will halt on the next transition and so is not a winner. So $t_1 = 1$ and $s = s_1$, but then $M$ will loop (two cases to check: $s = A$ and $s = B$). In all cases when $d = R$, $M$ fails to win so $d = L$.

Now we know that the only transition that moves right is the one on $(A, 0)$. This implies that $M$ can never move right past a 1 that has already been written. It follows that the penultimate transition must be a move right. I.e., it must be a transition on $(A, 0)$. But the successor state for this transition is $B$, so we must have $s_1 = A$ and $s_2 = B$. Now if $s = A$, $M$ will either fail to terminate or will halt and lose on the fourth transition (depending on the value of $t_2$). We conclude that $s = B$, so the transition function looks like this:

$\begin{array}{l} (A, 0) \mapsto (1, R, B) \\ (B, 0) \mapsto (t_1, L, A) \\ (A, 1) \mapsto (t_2, L, B) \\ (B, 1) \mapsto (1, X, H) \end{array}$

We now have just four cases to check and unsurprisingly the only possibility that makes $M$ terminate after writing four 1s is the one with $t_1 = t_2 = 1$.

Answer 2

Let allow me to write down this table of possible rules:

A0|0LA|1LA|0RA|1RA|0LB|1LB|0RB|1RB|0LH|1LH|0RH|1RH

A1|0LA|1LA|0RA|1RA|0LB|1LB|0RB|1RB|0LH|1LH|0RH|1RH

B0|0LA|1LA|0RA|1RA|0LB|1LB|0RB|1RB|0LH|1LH|0RH|1RH

B1|0LA|1LA|0RA|1RA|0LB|1LB|0RB|1RB|0LH|1LH|0RH|1RH

There will be indeed 20736 TMs, but you can easily eliminate many of them. You probably know that Robert Munafo in his site concluded that the first rule, for A0 must be 1RB, so, writing one and move to the right. So our table is:

A0|1RB

A1|0LA|1LA|0RA|1RA|0LB|1LB|0RB|1RB|0LH|1LH|0RH|1RH

B0|0LA|1LA|0RA|1RA|0LB|1LB|0RB|1RB|0LH|1LH|0RH|1RH

B1|0LA|1LA|0RA|1RA|0LB|1LB|0RB|1RB|0LH|1LH|0RH|1RH

This gives only 12^3 = 1728 TMs. We can reduce it further if we note that in all rules we can leave only one possibitily for the halting rule: 1RH (or 1LH, no matter for the result). So:

A0|1RB

A1|0LA|1LA|0RA|1RA|0LB|1LB|0RB|1RB|1RH

B0|0LA|1LA|0RA|1RA|0LB|1LB|0RB|1RB|1RH

B1|0LA|1LA|0RA|1RA|0LB|1LB|0RB|1RB|1RH

This leaves us with 729 TMs. Now we can note that in the rule B0, we can eliminate the possibilities 0RA, 1RA, 0RB, 1RB and 1RH, first four lead to infinite loop, the last one lead to 2 ones. Our table is:

A0|1RB

A1|0LA|1LA|0RA|1RA|0LB|1LB|0RB|1RB|1RH

B0|0LA|1LA|0LB|1LB

B1|0LA|1LA|0RA|1RA|0LB|1LB|0RB|1RB|1RH

324 TMs for now. Don't worry, we mustn't shall check them all, we need to explore 4 branches from 0LA, 1LA, 0LB, 1LB in rule B0. Now we can create the sub-ruleset for every branch, for example:

Branch B0|0LA

A1|0LA|1LA|0RA|1RA|0LB|1LB|0RB|1RB

B1|1RH

Note that one rule must be halting anyways, otherwise TM will works infinitely regardless to complexity of its behavior. In Branch B0|0LA, this rule must be B1|1RH, and in A1 we can eliminate the halting rule.

In every branch you will have 8 TMs, so there are 32 TMs to check. Simulate them on http://morphett.info/turing/turing.html to figure out their behavior.