Let $\Sigma$ be Radó's Busy Beaver function, and define $\Delta(n) \ = \ \Sigma(n+1) - \Sigma(n)$ for all $n \in \mathbb{N}$.

Question: Does the function $\Delta$ eventually dominate every computable function $f: \mathbb{N} \rightarrow \mathbb{N}$?

Sources: "A note on Busy Beavers and other creatures" (1996), by Ben-Amram, Julstrom, and Zwick, contains the conjecture that for any computable function $f$, there exists a constant $N_f$ such that $\forall n \gt N_f, \Sigma(n+1) > f(\Sigma(n))$. In support of this they prove the weaker result that for any computable function $f$, $\Sigma(n+1) > f(\Sigma(n))$ for infinitely many values of $n$. (Considering $f(x) = 2x$, for example, the conjecture implies an affirmative answer to the title question.)

NB: This question is the most elementary case of one that I posted on math.SE two weeks ago, but which has received no satisfactory answer.

  • 4
    $\begingroup$ Note that $\Delta(n)$ cannot be computable since $\Sigma(n) = \Sigma_{i< n} \Delta(n) + \Sigma(0)$. That means that the running time (or space) of any TM computing $\Delta$ cannot be dominated by a computable function. On the other hand, can you show that $\Delta$ eventually dominates the constant function $1$? $\endgroup$
    – Kaveh
    Nov 28 '11 at 6:55
  • 2
    $\begingroup$ The answer to this question could depend on the specific model of a Turing machine so this isn't really a question about computation and any answer won't be particularly enlightening. $\endgroup$ Nov 28 '11 at 14:29
  • $\begingroup$ @Kaveh: Good point; i.e., if $\Delta$ were computable, then (by the equation you wrote) $\Sigma$ would be computable, which provably is not the case. But, of course, the non-computability of $\Delta$ does not imply eventual domination of every computable function. $\endgroup$
    – r.e.s.
    Nov 28 '11 at 14:44
  • 1
    $\begingroup$ Lance is right, $\Delta$ is more model specific in a way that $\Sigma$ is not. The question you are asking is not robust w.r.t. the change of models whereas for example uncomputablilty of $BB$ is a robust theorem. I would think the more natural question would be about $\Delta(n) = \Sigma(n+k)-\Sigma(n)$ for some suitably large but consent $k$ (depending on the particulars of the model). $\endgroup$
    – Kaveh
    Nov 28 '11 at 21:35
  • 2
    $\begingroup$ @Kaveh & Lance Fortnow: Sorry to be so slow to appreciate the "robustness" issue. Using an argument of $n + const$ rather than $n+1$ might be more natural, as would a slight change in the definition of $\Sigma$ to count the ones that remain after halting only if they occur in a single run. (This is more robust w.r.t. definitions of "output".) The paper I cited does that, and calls the resulting function $num$; interestingly, unlike the case for $\Sigma$, they succeed in proving that for any computable function $f$, there is a constant $c_f$ such that $\forall n, num(n+c_f) \gt f(num(n))$. $\endgroup$
    – r.e.s.
    Nov 29 '11 at 3:22

Your Answer

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

Browse other questions tagged or ask your own question.