5
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – r.e.s. Nov 14 '11 at 16:45
  • 2
    $\begingroup$ 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$). $\endgroup$ – r.e.s. Nov 15 '11 at 19:03
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "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$. $\endgroup$ – r.e.s. Jan 9 '17 at 2:48
  • $\begingroup$ 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. $\endgroup$ – cadare Jan 12 '17 at 7:41
  • $\begingroup$ 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).$$ $\endgroup$ – r.e.s. Jan 22 '17 at 20:31
  • $\begingroup$ (... 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$"). $\endgroup$ – r.e.s. Jan 22 '17 at 20:31
-2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Srivatsan Nov 14 '11 at 13:36
  • $\begingroup$ (FYI: I've switched from $D$ to the standard $\Delta$ notation for the forward difference.) $\endgroup$ – r.e.s. Nov 16 '11 at 4:04

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.