# Does the $k$th forward difference of Radó's $\Sigma$ eventually dominate every computable function?

Let $\Sigma$ be Radó's Busy Beaver function, and let $\Delta[\Sigma]$ denote the forward difference of $\Sigma$, such that $\Delta[\Sigma] \ (n) = \Sigma(n+1) - \Sigma(n)$ for all $n \in \mathbb{N}$. Define $\Delta^0[\Sigma] = \Sigma$, and $\Delta^{k+1}[\Sigma] = \Delta[\Delta^{k}[\Sigma]]$, for all $k \in \mathbb{N}$.

Definition: Given functions $f,g$ with the common domain $\mathbb{N}$ and codomains that are subsets of $\mathbb{Z}$, $g$ is said to eventually dominate $f$ iff $g(n) > f(n)$ for all sufficiently large $n\in\mathbb{N}$.

Question: Is it the case that for all $k \in \mathbb{N}$, the function $\Delta^k [\Sigma]$ eventually dominates every computable function $f: \mathbb{N} \rightarrow \mathbb{N}$?

(I believe this is the case, but do not know how to prove it. Any pointers or sources on proving this -- or disproving it, if I'm wrong?)

Here's a difference table showing all the known values for these sequences:

     n:  0      1      2      3      4      5     ...
------------------------------------------------
Σ:  0      1      4      6      13    ≥4098  ...
ΔΣ:  1      3      2      7     ≥4085  ...
ΔΔΣ:  2     -1      5     ≥4078  ...
ΔΔΔΣ: -3      6     ≥4073  ...
ΔΔΔΔΣ:  9     ≥4067  ...
ΔΔΔΔΔΣ: ≥4058  ...


Known 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 that $\Delta[\Sigma]$ eventually dominates every computable function.)

Motivation: In the "Busy Beaver game" class of Turing machines, which eventually halt after starting with a blank tape, the "score" of a machine is the number of $1$s remaining on the tape after halting. A variant of Kolmogorov complexity $C: \mathbb{N} \rightarrow \mathbb{N}$ defines $C(n)$ to be the least $k$ such that $n$ is the score of some $k$-state machine. (cf "Computability and Logic" by Boolos, Burgess & Jeffrey, 2007, p229.) I believe I can show that if the first difference $\Delta[\Sigma]$ eventually dominates every computable function, then this $C$ is not monotonically nondecreasing, i.e., there exist $m \lt n$ such that $C(m) \gt C(n)$.

NB: Due to receiving no satisfactory answer here, I've posted the simplest case of this question on cstheory.SE.

For the eventual conclusion "there exist $m<n$ such that $C(m)>C(n)$" it seems to be easier just to prove that for some $k$ there exists a $k$-state machine with a score higher than the number of possible $k$-state machines. Then by the pigeonhole principle there has to be a number less than this that is reached only by a machine with $>k$ states.

Depending on the details, there are at most about $(6k)^{2k}$ different $k$-state machines, and this is easily a computable function. Therefore if add some initial states that preload a large enough $k$ (which can be done in $O(\log k)$ states) we will eventually reach a machine with a score that is high enough relative to its size.

• Good points. Which approach is easier depends on how hard it is to prove the domination result for the first difference of $\Sigma$ (and maybe that's harder than I thought, assuming it's true!). But given that result, and the fact that it's easy to show $C(\Sigma(k-1) + 1) = C(\Sigma(k)) = k$, the non-monotonicity conclusion follows readily by considering the number of $k$-state machines as a computable function of $k$ that's eventually dominated by $\Sigma(k) - \Sigma(k-1)$. – r.e.s. Nov 14 '11 at 16:45
• Hmmm ... I upvoted your reply although it's not an answer to my question -- not realizing that this removes the question from the "unanswered" list. I really would like to have a good answer re the $k$th difference of $\Sigma$. I think it would be a noteworthy result even to hold for only $k = 1$ (but I suspect it either holds for no positive $k$, or else it holds for all positive $k$). – r.e.s. Nov 15 '11 at 19:03

Edit: my original answer confused the definition of dominate (which is not an easy definition to get from Google, btw). I decided to delete that (non)answer and replace with a answer. Here goes.

For $k=0$, $\Delta^0[\Sigma]=\Sigma$. Let $g$ be any computable function. Then there is a $d$-state Turring machine that computes $g$. Let $m\in\mathbb{N}$ be sufficiently large such that $m≥C(m)+d+b$ where $C(m)$ is the number of states to print $m$ on a blank tape, $d$ is the number of states to compute $g$ and $b$ is the number of states to compute the composite of the two machines and add 1. That is, there is a machine $M$ with fewer than $m$ states such that $M(0)=g(m)+1$. This is possible because $m$ becomes increasingly larger than $C(m)$ and $d+b$ is a constant for a given function $g$. Now, for all $n≥m$, $\Sigma(n)≥g(n)$. That means that $g$ is dominated by $\Sigma$ from $m$ on.

Intuitively, for a computable functions $g$, eventually for large $n$, there is an $n$-state Turring machine that computes $g(n)$ from a blank tape. That means the busy beaver for $n$ is at least $g(n)$, probably much higher.

Now for $k=1$, $\Delta^1[\Sigma](n)=\Sigma(n+1)-\Sigma(n)$. Let $f$ be a computable function (to show that $f$ is dominated by $\Delta^1[\Sigma]$. Let's suppose $f$ is not dominated by $\Delta^1[\Sigma]$ (to show contradiction). That means for all $n$, there is some $m≥n$ such that $f(m)≥\Sigma(m+1)-\Sigma(m)$.

Let $n$ be an arbitrary natural number. Then there exists $m≥n$ such that $f(m)≥\Sigma(m+1)-\Sigma(m)$. Let's suppose that $\Sigma(m+1)-\Sigma(m)≥\Sigma(m)$. Then, $f(m)≥\Sigma(m)$. As shown above, eventual $f(m)$ is dominated by $\Sigma(m)$, so this is a contradiction. So, $\Sigma(m+1)-\Sigma(m)≥\Sigma(m)$ is false.

Let's suppose that $\Sigma(m+1)-\Sigma(m)≥\Sigma(m-c)$, where $0<c<m$. Then define a function $f'(n-c)=f(n)$, which is computable if $f$ is. Now $f'(m-c)≥\Sigma(m-c)$, which means $f'$ is not dominated by $\Sigma$. This is a contradiction. So $\Sigma(m+1)-\Sigma(m)≥\Sigma(m-c)$ is false. Therefore, $\Sigma(m+1)-\Sigma(m)<\Sigma(m-c)$. Now let $c=m-1$. Then $\Sigma(m+1)-\Sigma(m)<\Sigma(1)$. Or, rearranging: $\Sigma(m+1)<\Sigma(m)+1$. But $\Sigma$ is always strictly increasing. This is a contradiction. Therefore, $f$ is eventually dominated by $\Delta^1[\Sigma]$ or $f$ is not computable.

• "Suppose there is a computable function, $k$, that $\Delta[\Sigma]$ does not dominate. Then, $k$ is an upper bound on $\Delta[\Sigma]$. That is to say that, for some $m$, all $n>m$: $k(n)≥\Sigma(n+1)-\Sigma(n)$" ... No, you have the quantifiers in the wrong order; rather, it would be $$k\text{ is not eventually dominated by }\Delta\Sigma\\ \iff \lnot(\exists m\forall n>m\ (k(n) < \Delta\Sigma(n)))\\ \iff\forall m\exists n>m\ (k(n)\ge\Delta\Sigma(n)).$$ In particular, this does not imply that such $k$ is an eventual upper bound on $\Delta\Sigma$. – r.e.s. Jan 9 '17 at 2:48
• Thanks for the correction. I have changed the answer. I think I have it for k=1, but give me a day or two to clean up the answer. The basic idea is that if a computable function is not dominated by the forward difference, then that forward difference has to grow very slowly, otherwise a truncated version of the same computable function will not be dominated by $\Sigma$, a contradiction. – cadare Jan 12 '17 at 7:41
• There still seems to be "quantifier confusion". Let $S$ denote the supposition that there is a computable $f$ not eventually dominated by $\Delta\Sigma$. You appear to argue that $S$ leads to a contradiction regardless of whether a certain proposition $A$ is true or false, thus implying the desired conclusion that $S$ is false: $$\lnot(S\land A) \land \lnot(S\land\lnot A)\implies \lnot S$$ where the proposition in question is $$A:\quad\exists c\forall m>c,\ \ \Delta\Sigma(m)\ge\Sigma(m-c)$$ and its negation is $$\lnot A:\quad\forall c\exists m>c,\ \ \Delta\Sigma(m)< \Sigma(m-c).$$ – r.e.s. Jan 22 '17 at 20:31
• (... cont'd) Although you show that $S\land A$ is false (because it implies the falsehood that $f$ is not eventually dominated by $\Sigma$), you have not shown, as required, that $S\land\lnot A$ is false. It isn't sufficient to show that $\Delta\Sigma(m)\lt\Sigma(m-c)$ is false for some $c$ and $m$ (per your "let $c=m−1$"). – r.e.s. Jan 22 '17 at 20:31

Use http://mathworld.wolfram.com/NewtonsForwardDifferenceFormula.html to get $D^k [z] (n)>f(k,n)z(n+k)$ for some computable $f(k,n)$ and every strictly increasing positive function $z$. Thus if $g(n)>D^k [z](n)$ for some computable $g$, then there is a computable bound on any $z(n+k)$. Contradiction.

• I am still puzzled. Where do you get the first sentence from? It might also help if you specify exactly what $f(k,n)$ is. – Srivatsan Nov 14 '11 at 13:36
• (FYI: I've switched from $D$ to the standard $\Delta$ notation for the forward difference.) – r.e.s. Nov 16 '11 at 4:04