# Does $\Sigma(n+1)-\Sigma(n)$ eventually dominate every computable function?

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.

-
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
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
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
@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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9189212918281555, "perplexity": 263.1128869270015}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2014-42/segments/1414637900185.53/warc/CC-MAIN-20141030025820-00018-ip-10-16-133-185.ec2.internal.warc.gz"}