Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Standard busy beaver function draws attention to final count of nonzero symbols on tape. We could instead look at largest amount of nonzero symbols appearing on tape at any point of computation. This function's lower bound would be $\Sigma(n)$ and upper bound would be $S(n)$ (max shifts function). Was there made any research on such functions? If so, are there any known values for this?

share|cite|improve this question
its likely just as hard as BB fn which is uncomputable. one could also count the total # of 1's ever written, etc... – vzn Apr 11 '14 at 16:36
up vote 8 down vote accepted

Suppose there is a machine using $n$ states which, at some point, has $X$ nonzero symbols on the tape. One can build a machine with $O(n)$ states which simulates a run of the original machine with a tape alphabet of three symbols $\{0,1,2\}$, with the following small change: whenever the original machine changes $1$ to $0$, the new machine changes it to $2$; whenever the tape is read, $2$ is interpreted as $0$. The new machine ends up with $Y \in [X,2X]$ nonzero symbols on the tape (we get $\Theta(X)$ instead of $X$ since the simulation requires using two symbols for each original symbol). So your new function, let's call it $F(n)$, satisfies $B(n) \leq F(n) \leq B(O(n))$.

share|cite|improve this answer
Is there any way to sharpen the $O()$ and $\Theta()$? Just curiosity (probably best left to the OP) – vonbrand Jan 27 '13 at 3:32
I have no idea. My guess is that on the scale from $B(n)$ to $B(O(n))$, $F(n)$ is closer to the latter. It may be possible to prove a lower bound on $F(n)$ somehow. Give it a try! – Yuval Filmus Jan 27 '13 at 6:34

Your function (call it $F$) obviously satisfies $$\Sigma(n) \le F(n) \le space(n)$$ where $space(n)$ is the maximum number of tape squares visited by any $n$-state halting TM in the same class as those considered in the definition of $\Sigma$. Furthermore, $$space(n) \le \Sigma(3n-1)$$ as proved in the following paper:

Ben-Amram, A. M., B. A. Julstrom, and K. Zwick. "A Note on Busy Beavers and Other Creatures." Mathematical Systems Theory 29.4 (1996).

Therefore $$\Sigma(n) \le F(n) \le \Sigma(3n-1)$$

share|cite|improve this answer

Your Answer


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.