Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
In case of $BB(2)$, i would just write down every possible two-state machine and show that they produce lower scores than 4. –  Malte Mar 17 '12 at 19:50
2  
i thought so to, but there are ( 2*2*(2+1) )^(2*2) = 20,736 machines –  Alan Mar 17 '12 at 20:08
    
Well, that was very silly of me then. The article you're looking for is Lin, Shen and Radó, Tibor (1965), Computer Studies of Turing Machine Problems, Journal of the ACM, Vol. 12, No. 2 (April 1965), pp. 196–212. Sadly, I can't seem to find a download link. Note, moreover, that Wikipedia says that most of the proof for $BB(3) = 6$ was obtained by the aid of computers. –  Malte Mar 17 '12 at 20:51
    
yep, that's the article i need. Can't find a link also. think this one can be solved without a computer - got it for homework :) –  Alan Mar 17 '12 at 21:07
    
For what is worth, the article has no details of the computation of $BB(2)$, and instead concentrates on $BB(3)$. The notation they use is $\Sigma$ for $BB$. "As an exercise in a seminar, it has been shown that $\Sigma (2) = 4$." It really can be done by hand, actually, in spite of the large number of Turing machines that seem involved. –  Andres Caicedo Mar 18 '12 at 2:11
add comment

2 Answers 2

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$.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.