Busy Beaver - Proof for BB(2) = 4 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.
 A: 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$.
