# calculate lower bound of busy beaver

Let $m$ be the number of states (without the halting-state) of a deterministic turing-machine with $\Sigma$ = {} and $\Gamma$ = {$\square$, 0, 1}. Let $G(m)$ be the maximum number of ones, which can be generated by a deterministic turing-machine, before going into the halting-state. Prove that $G(m)$ $\in$ $\Omega(2^m)$. (This is about the so called "busy beaver" problem, with the mathematical rado-function $\Sigma(N)$ or $bb(N)$.) Who can me help with that?

• Please don't change the content/title of the question to a completely different one. Check if the answer is ok for the original question, accept it (or ask for some clarifications), and then evaluate whether to ask a new different question or not. – Vor Apr 16 '13 at 12:05
• Also note that all revisions are archived permanently, so all attempts at deleting your record here are futile. (Also, we might just ban you if you continue.) – Raphael Apr 16 '13 at 13:23

## 1 Answer

All you need to do is show that a machine with $m$ states can halt with $\Omega(2^m)$ 1's on the tape.

There are many ways to prove this. This is just one suggestion, and it may be sub-optimal.

Let $T$ be a machine that on a word of the form $0^i1^j$, when the head is in the leftmost $0$, halts with $0^i1^{2j}$ on the tape and the head at the leftmost $0$.

$T$ is a fixed machine, and thus has $t$ states, for a constant $t$.

We now construct the machine $M_i$ as follows: first, $M_i$ writes $0^i1$ on the tape, using $i+1$ states. It then moves the head to the left most cell, using another single state. Then, if the leftmost cell is $0$, it erases it and passes control to $T$ (this requires $t+1$ states). If the leftmost cell is $1$, it halts.

$M_i$ has $i+2+t$ states, and after it halts the tape contains exactly $2^i$ 1's (since in every call to $T$ we double the number of 1's, and we call $T$ $i$-times).

Thus, if $M_i$ has $m$ states, it halts with $\frac{2^m}{t+2}\in\Omega(2^m)$ 1's, and we are done.