6
$\begingroup$

A famous 1962 paper by Tibor Radó shows that the "busy beaver" function $h$ (which computes the maximal number of steps for which a halting Turing machine with $n$ states can run for) satisfies the property

  • (A) for every computable total function $f\colon\mathbb{N}\to\mathbb{N}$ we have $h(n) \geq f(n)$ eventually (i.e., there exists $N$ such that for all $n\geq N$ we have $h(n) \geq f(n)$)

Now what is very easy to prove is the weaker

  • (B) for every computable total function $f\colon\mathbb{N}\to\mathbb{N}$ we have $h(n) \geq f(n)$ infinitely often (i.e., for each $N$ there exists $n\geq N$ such that $h(n) \geq f(n)$)

(because if there were a computable $f$ such that $f(n)\geq h(n)$ eventually we could find one such that $f(n)\geq h(n)$ always, and then we could solve the halting problem for $n$ state Turing Machines by waiting at most $f(n)$ steps).

Now Radó's proof is fairly opaque, it looks like a bit of magic, I can't figure out the deep reason why he is able to prove (A) and not just (B): is it something really specific to the busy beaver function, or is there some general trick that makes it possible to derive (A) from (B)? So:

Does an increasing function $h$ that satisfies (B) automatically satisfy (A)? If not, is there some simple condition we can add to get (A) from (B) that would "explain" Radó's proof?

And, if the previous questions do not make this trivial:

Are there Turing degrees containing functions $h$ satisfying (B) but no function satisfying (A)?

$\endgroup$
  • 3
    $\begingroup$ You might want to include the condition "increasing" on all of this - a function which equals the busy beaver function on even values and $0$ on odd values clearly satisfies $B$ but not $A$. (EDIT: Actually, that doesn't make things much better. You can just take a function defined as $g(n)=\begin{cases}g(n-1)&&\text{if }f(n)\leq g(n-1) \\ BB(n)&&\text{otherwise}\end{cases}$ where $BB$ is the busy beaver function and $f$ is some computable function. Then $g$ satisfies (B) but not (A). I don't have the background to answer your second question though) $\endgroup$ – Milo Brandt Jan 14 '16 at 23:51
4
$\begingroup$

I haven't read Radó's proof closely, but the following way to (A) seems to be pretty straightforward, at least for the busy-beaver output function $BB_o$, where $BB_o(n)$ is the maximal number of 1s left on the tape after an $n$-state machine terminates:

Let $f$ be any total computable function. Then there is a number $m$ such that the program

 1. X = m;
 2. X = f(X);
 3. X = X+1;
 4. output X

can be implemented in a machine with exactly $m$ states. (Basically this is just a matter of observing that we can construct the number $2^k$ using $O(k)$ states, for example). Furthermore we can insert any number of X=X+1 between steps 1 and 2, each costing exactly one state (namely move left and write a 1 on the tape). So the above program can actually be implemented in $m$ states for all sufficiently large $m$.

Now if $f(m) \ge BB_o(m)$ for infinitely many $m$, then one of those $m$s must be sufficiently large, but that leads to a contradiction, because the machine alluded to above has $m$ states, and so by definition $BB(m)$ must be at least $f(m)+1$.

Thus we must have $f(n) < BB_o(m)$ eventually.

Your goal is for the busy-beaver time function, $BB_t(n)$ is maximum number of steps an $n$-state machine can take before it terminates. But this easy reduces to the above case: since $BB_t(n)\ge BB_o(n)$, a function that exceeds $BB_t(n)$ infinitely often must also exceed $BB_o(n)$ infinitely often -- which we've just seen is impossible for computable functions.


For a $h$ that satisfies (B) but not (A) we can take

$$ h(n) = \begin{cases} 42 & \text{if } n=0 \\ BB(n) & \text{if } h(n-1) < (n-1)^2 \\ h(n-1)+1 & \text{otherwise} \end{cases} $$

Then $h(n) < n^2$ infinitely often, so $f(n)=n^2$ is a counterexample to (A).

On the other hand $h(n)=BB(n)$ infinitely often, so an $f$ that eventually exceeds $h(n)$ would exceed $BB(n)$ infinitely often, which is impossible by the above argument.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks to you and Milo Brandt for the counterexample. Your proof of (A) for the busy beaver function is indeed much nicer than Radó's original, so that much is clear. What's still not 100% clear in my mind, however, is exactly what ingredients were used. For example, suppose we let $h(n)=\max\{\varphi_e(e):0\leq e\leq n\land\varphi_e(e)\downarrow\}$ for a "standard" numbering of the partial computable functions $\varphi_e$. We should be able to similarly show (A) but the details are still confused for me (we probably need s-m-n with prim. recursive $s$ or something). $\endgroup$ – Gro-Tsen Jan 15 '16 at 14:44
  • $\begingroup$ @Gro-Tsen: Oops, I didn't notice that Milo Brandt's counterexample was essentially the same as mine -- I was confused because it looked like it depended on a particular $f$, and so wasn't really on point for a counterexample of properties that quantify over $f$. But it looks now like that was just a harmless name clash. $\endgroup$ – hmakholm left over Monica Jan 15 '16 at 14:50
2
$\begingroup$

After some digging I can answer the part about Turing degrees in my own question. It turns out that condition (B) is, indeed, weaker, than condition (A) at the Turing degree level. More precisely:

  • A Turing degree $\mathbf{a}$ is "hyperimmune" iff there is an $\mathbf{a}$-computable function $h$ that satisfies (B), i.e., that is not dominated by any computable function $f$. (See, e.g., Downey & Hirschfeldt, Algorithmic Randomness and Complexity (Springer, 2010), definition 2.17.1 on p. 67, or Miller & Martin, "The Degrees of Hyperimmune Sets", Z. Math. Logik 14 (1968), corollary 1.1 on p. 160.)

  • A Turing degree $\mathbf{a}$ is satisfies $\mathbf{a}'\geq 0''$ (when $\mathbf{a} \leq 0'$ this condition is called "high") iff there is an $\mathbf{a}$-computable function $h$ that satisfies (A), i.e., that dominates any computable function $f$. (See, e.g., Downey & Hirschfeldt, Algorithmic Randomness and Complexity (Springer, 2010), theorem 2.33.7 on p. 97, or Martin, "Classes of Recursively Enumerable Sets and Degrees of Unsolvability", Z. Math. Logik 12 (1966), lemmata 1.1 and 1.2.)

So my question was whether there is a Turing degree which satisfies the first but not the second. But in fact, any computably enumerable degree other than $0$ is hyperimmune (this was essentially my argument why busy beaver satisfies (B): see here, which in fact answers my question inter alia), and not all such degrees are high (e.g., there exist low c.e. degrees).

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

(Posting a second answer for clarity because this relates to a different part of my question.)

Inspired by Henning Makholm's answer, I can prove the following statement which does not make any reference to a specific model of computability like Turing machines:

Let $\varphi_e$ be a standard enumeration of partial computable functions $\mathbb{N}^k\rightharpoonup\mathbb{N}$: the crucial fact in “standard” is that the s-m-n theorem holds with primitive recursive substitution function, i.e., there exists $s$ primitive recursive such that $\varphi_e(m,n) = \varphi_{s(e,m)}(n)$.

Let $h\colon\mathbb{N}\to\mathbb{N}$ be defined by $h(n) := \max\{\varphi_e(e) : 0\leq e\leq n \land \varphi_e(e)\downarrow\}$. (It is fairly obvious that $h$ satisfies (B).)

To be proven: In fact, $h$ satisfies (A), i.e., if $f\colon\mathbb{N}\to\mathbb{N}$ is computable then there exists $N$ such that $h(n) \geq f(n)$ for $n\geq N$.

Proof: Let $\gamma\colon\mathbb{N}\to\mathbb{N}$ be the diagonal Ackermann function. (What we need is that $\gamma$ is computable, increasing, and eventually dominates all primitive recursive functions, i.e. satisfies the analogue of (A) for primitive recursive $f$.)

Let $f\colon\mathbb{N}\to\mathbb{N}$ be any computable function. We want to show that $h(n) \geq f(n)$ for all $n$ sufficiently large. We define $g(k, j) := \max\{f(i) : 0\leq i\leq \gamma(k)\}$ (the variable $j$ is ignored). Let $p$ be an index for $g$, i.e., $g = \varphi_p$.

Now we have $\varphi_{s(p,k)}(j) = \varphi_p(k,j) = g(k,j) = \max\{f(i) : 0\leq i\leq \gamma(k)\}$ (again, $j$ is ignored). So if $n \geq s(p,k)$ and $i \leq \gamma(k)$ then $h(n) \geq f(i)$. In particular, if $s(p,k) \leq n \leq \gamma(k)$ then $h(n) \geq f(n)$.

But since $s(p,k+1)$ is a primitive recursion function of $k$, there exists $k_0$ such that if $k \geq k_0$, we have $\gamma(k) \geq s(p,k+1)$. Then if $n \geq s(p,k_0)$, there clearly exists $k$ such that $s(p,k) \leq n \leq \gamma(k)$, which implies $h(n) \geq f(n)$ as just explained. This proves that $h$ eventually dominates $f$. QED

Note that the proof works verbatim if we define $h$ by $h(n) := \max\{\varphi_e(0) : 0\leq e\leq n \land \varphi_e(0)\downarrow\}$ (the argument to $\varphi_e$ is only there because it is sometimes disturbing to consider and enumerate partial computable functions of $0$ arguments).

Applying this to Turing machines, it says that the function $h$ which maps $n$ to the maximal possible output of those among the $n$ first Turing machines which halt (for any “reasonable” numbering), eventually dominates any computable function. Since the maximal possible halting output of the $n$ first Turing machines is certainly at most equal to the maximal possible halting output of the at-most-$n$-state Turing machines, we recover Radó's result on the standard busy beaver function. But what I find interesting about this approach is that if makes it clear that we need to assume very little on the numbering: for any programming language in which composition is primitive recursive (a very weak requirement), the maximal possible halting output of the $n$ first programs will eventually dominate any computable function.

(How was I inspired by Henning Makholm's answer? Basically he uses $\gamma(k) = 2^k$ in saying “we can construct the number $2^k$ in $O(k)$ states”, something which is sufficient for the case of Turing machines and if we just count their number of states: it is this key “bootstrap” argument that I failed to understand in Radó's proof and that I sought to make explicit above.)

| cite | improve this answer | |
$\endgroup$

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.