Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
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$? –  Kaveh Nov 28 '11 at 6:55
2  
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. –  Lance Fortnow Nov 28 '11 at 14:29
    
@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. –  r.e.s. Nov 28 '11 at 14:44
1  
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). –  Kaveh Nov 28 '11 at 21:35
2  
@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))$. –  r.e.s. Nov 29 '11 at 3:22
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.