<p>Let $\Sigma$ be Radó's <a href="http://en.wikipedia.org/wiki/Busy_beaver#The_busy_beaver_function_.CE.A3" rel="nofollow noreferrer">Busy Beaver function</a>, and define  $\Delta(n) \ = \ \Sigma(n+1) - \Sigma(n)$ for all $n \in \mathbb{N}$. </p>

<p><strong>Question</strong>: Does the function $\Delta$ eventually dominate every computable function $f: \mathbb{N} \rightarrow \mathbb{N}$?</p>

<p><strong>Sources</strong>: <a href="http://www.springerlink.com/content/3r25m95gu015y6xd/" rel="nofollow noreferrer">"A note on Busy Beavers and other creatures"</a> (1996), by Ben-Amram, Julstrom, and Zwick, contains the <em>conjecture</em> that for any computable function $f$, there exists a constant $N_f$ such that $\forall n \gt N_f, \Sigma(n+1) &gt; f(\Sigma(n))$. In support of this they prove the weaker result that for any computable function $f$, $\Sigma(n+1) &gt; 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.) </p>

<p><strong>NB</strong>: This question is the most elementary case of one that I <a href="https://math.stackexchange.com/questions/81928/does-the-kth-forward-difference-of-rados-sigma-eventually-dominate-every-c">posted on math.SE</a> two weeks ago, but which has received no satisfactory answer.</p>

CC BY-SA 3.0
2011-11-28T06:55:17.837Z
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
CC BY-SA 3.0
2011-11-28T14:29:10.463Z
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
CC BY-SA 3.0
2011-11-28T14:44:34.737Z
@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.
CC BY-SA 3.0
2011-11-28T15:23:53.503Z
@Lance Fortnow: Evidently $\Delta$ is not more "model specific" than $\Sigma$. Is the behavior of $\Sigma$ also "not particularly enlightening"?
r.e.s.
CC BY-SA 3.0
2011-11-28T21:35:08.313Z
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
CC BY-SA 3.0
2011-11-29T03:22:35.200Z
@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.
<reference-request><computability>
Does $\Sigma(n+1)-\Sigma(n)$ eventually dominate every computable function?
r.e.s.
# Does $\Sigma(n+1)-\Sigma(n)$ eventually dominate every computable function?

(Asked by: username_0 on 2011-11-28)

Let $\Sigma$ be Radó's [Busy Beaver function](http://en.wikipedia.org/wiki/Busy_beaver#The_busy_beaver_function_.CE.A3), 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"](http://www.springerlink.com/content/3r25m95gu015y6xd/) (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](https://math.stackexchange.com/questions/81928/does-the-kth-forward-difference-of-rados-sigma-eventually-dominate-every-c) two weeks ago, but which has received no satisfactory answer.

**Tags:** reference-request, computability
> **Comments:**
> **username_1**: 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$?  
> **username_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.  
> **username_0**: @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.  
> **username_0**: @Lance Fortnow: Evidently $\Delta$ is not more "model specific" than $\Sigma$. Is the behavior of $\Sigma$ also "not particularly enlightening"?  
> **username_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).  
> **username_0**: @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))$.  

---

## 0 answers

