1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Vor Apr 16 '13 at 12:05
  • 1
    $\begingroup$ 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.) $\endgroup$ – Raphael Apr 16 '13 at 13:23
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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