[Solved]: Faster growing busy beaver function

Problem Detail: 

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?

Asked By : Wojowu

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9031

3.2K people like this

 Download Related Notes/Documents