# Complexity relative to the graph of the Busy-Beaver function

This question is inspired by the comments made on this other question that I asked, and by an attempt to provide an explicit example of a complexity question beyond the Turing degree $$\mathbf{0}$$. (And like the former question, I'm not sure whether this is more appropriate here or on MathOverflow.)

Let $$\Gamma_{\mathrm{BB}}$$ be the graph of the Busy-Beaver function, i.e., $$\Gamma_{\mathrm{BB}}$$ is the set of $$(n,v)$$ such that $$v = \mathrm{BB}(n)$$ (I hope the exact details of how the Busy-Beaver function is defined aren't relevant for the question I'm about to ask! but let's say that $$\mathrm{BB}(n)$$ is the maximal number of execution steps that a Turing machine with $$n$$ states can take and eventually halt). Now consider Turing machines with $$\Gamma_{\mathrm{BB}}$$ as an oracle: i.e., they are allowed to ask the question “is $$v = \mathrm{BB}(n)$$?” at any point in their computation.

Since $$\mathrm{BB}$$ is in the same Turing degree $$\mathbf{0}'$$ as the halting problem $$H$$, such machines can indeed solve the halting problem (given a machine $$e$$ having $$n$$ states, simulate its execution while, at each step $$v$$, asking $$\Gamma_{\mathrm{BB}}$$ whether $$v = \mathrm{BB}(n)$$, and stop whenever either the machine stops or we know we've run more steps than a machine with $$n$$ steps can possibly go through).

Now I am interested in the time complexity for such machines with $$\Gamma_{\mathrm{BB}}$$ as an oracle: clearly the algorithm I described has an enormous complexity (comparable to $$\mathrm{BB}$$ itself!). So I am inclined to ask whether one can do better.

Specifically:

Question 1: Does the halting problem $$H$$ belong to any standard complexity class relativized to the $$\Gamma_{\mathrm{BB}}$$ oracle, like $$\mathbf{P}^{\Gamma_{\mathrm{BB}}}$$ (polynomial time), $$\mathbf{EXP}^{\Gamma_{\mathrm{BB}}}$$ (exponential time) or $$\mathbf{PR}^{\Gamma_{\mathrm{BB}}}$$ (primitive recursive in $$\Gamma_{\mathrm{BB}}$$)?

Note in particular that, if such is the case, once we can compute the halting problem, we can compute all computable sets in the same complexity (I mean, if $$H$$ is the halting problem, and $$\mathbf{R}$$ is the class of all computable sets, we have $$\mathbf{R} \subseteq \mathbf{P}^H$$ by letting the oracle do all the computational work, so a positive answer to question 1, say, for $$\mathbf{P}$$, would imply that $$\mathbf{R} \subseteq \mathbf{P}^{\Gamma_{\mathrm{BB}}}$$).

Question 2: Or, at the other extreme, is it perhaps true that $$\mathbf{P}^{\Gamma_{\mathrm{BB}}} \cap \mathbf{R}$$ (functions computable in polynomial time with $$\Gamma_{\mathrm{BB}}$$ as oracle, and which happen to also be computable without oracle) equals $$\mathbf{P}$$, i.e., that having access to $$\Gamma_{\mathrm{BB}}$$ as an oracle won't speed up the computation of any problem that's already computable? (Or replace $$\mathbf{P}$$ by any standard complexity class like the ones mentioned in the previous question.)

Really nice question(s). I don't fully follow Denis’ answer, so I'm going to try my own.

For question 1, I’m going to assume that you are familiar with Kolmogorov complexity (otherwise I could write a proof heavily using Kleene’s fixed point theorem, but such proofs tend to look like black magic, while Kolmogorov complexity is rather natural). Assume for the sake of contradiction that $$H$$ can be computed from oracle $$\Gamma_{BB}$$ in computably bounded time, and let $$f$$ be a computable bound.

First, I claim that for all $$n$$, the first $$2^{n+1}$$ bits of $$H$$ form a string $$x_n$$ of Kolmogorov complexity at least $$n$$. Indeed, if we knew $$x_n$$, this would allow us to know which programs of size $$\leq n$$ halt, so we could run all of them and return a string different from all the outputs of terminating programs of size $$\leq n$$, hence of Kolmogorov complexity $$>n$$. In other words, we can computably transform $$x_n$$ into a string of complexity $$>n$$, which by conservation of complexity implies $$K(x_n)>n$$ (I ommit the usual additive constant).

On the other hand, by our assumption the first $$2^{n+1}$$ bits of $$H$$ can be computably obtained from the first $$f(2^{n+1})$$ bits of $$\Gamma_{BB}$$. But $$\Gamma_{BB}$$ is very, very, sparse hence in particular, for infinitely many $$n$$, the string $$y_n$$ consisting of the first $$f(2^{n+1})$$ bits of $$\Gamma_{BB}$$ is all zeroes except perhaps for the the first, say, $$n/2$$ bits, and thus $$y_n$$ must have Kolmogorov complexity less than $$n/2$$ (it suffices to specify the first $$n/2$$ bits), which contradicts the fact that the first $$2^{n+1}$$ bits of $$H$$ can be computably obtained from $$y_n$$.

Question 2 goes right into current research in computability theory. Fortnow proposed a little while ago the concept of `low for speed’. An oracle $$X$$ is low for speed if it does not alter any computational complexity class. More precisely, $$X$$ is low for speed if any computable language $$L$$ that can be computed from oracle $$X$$ in time $$f$$ can be computed without $$X$$ in time $$poly(f)$$. While we do not have a full characterization of low for speed oracles, we know that:

• there exist non-computable ones, which can be taken to be recursively enumerable (Robertson Bayer. Lowness For Computational Speed. PhD thesis, University of California Berkeley, 2012)
• that they form a measure 0 set (Bienvenu Downey, https://arxiv.org/abs/1712.09710) but they form a meager set if and only if $$P \not= NP$$ (Bayer, ibid)
• that lowness for speed is not a Turing degree notion, but any $$X \geq_T \emptyset’$$ is not low for speed (Bienvenu-Downey, ibid)

From this last point, we know that $$\Gamma_{BB}$$ is not low for speed, so there is some computable language which can be computed much faster with $$\Gamma_{BB}$$ than without it. I'd have to think about it, but I believe we could cook up a language which is in $$\mathbf{P}^{\Gamma_{BB}}$$ but not in $$\mathbf{P}$$.

Here is a negative answer to question 1.

Let us assume that there is a computable function $$f$$ such that there is a Turing machine $$M$$ recognizing $$H$$ in time $$f(n)$$ with oracle $$\Gamma_{BB}$$. Let $$g$$ be a computable function bounding the maximal integer that $$M$$ can write on its tape on input of size $$n$$, for instance with binary encoding $$g(n)=2^{f(n)}$$.

On an input of size $$n$$, the machine $$M$$ can only call the oracle on pairs $$(x,y)$$ with $$y\leq g(n)$$. Since $$BB$$ is eventually bigger than $$g$$, this would mean that there is a recursive procedure that decides the halting problem, using only the value of $$BB$$ for machines of smaller size. So using recursive calls, a finite amount of data would be enough: the values $$BB(n)$$ for $$n\leq N$$, where $$N$$ is the threshold from where $$BB$$ is always bigger than $$g$$.

This would make $$H$$ recursive, since it would be recognized by a machine with a finite oracle.

I left too many gaps in the above explanation for it to be clear, so here is a more detailed proof. Assume we have a machine $$M$$, and a function $$g$$ as above. We take $$N$$ such that for all $$n\geq N$$, $$g(n). Here is a description of an algorithm $$A$$ solving the halting problem $$H$$. This algorithm $$A$$ has access to a lookup table for all values $$BB(k)$$ with $$k.

Here is the behaviour of $$A$$ on input $$\langle M_i\rangle$$ of size $$n$$.

• If $$n, use the lookup table to find $$BB(n)$$, and simulate $$M_i$$ for $$BB(n)+1$$ steps, answer NO if it does not finish within this time and YES otherwise.

• If $$n\geq N$$, then simulate $$M(\langle M_i\rangle)$$. Each time an oracle call is performed, asking for $$\Gamma_{BB}(x,y)$$, do the following:

• If $$x\geq n$$, have the oracle call return NO. This is correct because by choice of $$N$$, $$y$$ is necessarily strictly smaller than $$BB(x)$$.

• If $$x, recursively call $$A(\langle M' \rangle)$$ for all machines $$M'$$ of size $$x$$. This allows to fully simulate all machines of this size that halt, and compute the maximal running time $$BB(x)$$ among them. Comparing $$BB(x)$$ to $$y$$ allows to return the correct answer for the oracle call.

Since recursive calls are always performed on machines of smaller size, the algorithm $$A$$ always halts, and it is able to fully simulate the run of $$M$$ on $$\langle M_i\rangle$$. So it is a correct algorithm deciding the halting problem $$H$$, and we obtain a contradiction.

• OK, there's something that bothers me here: you prove that no set (not just specifically $H$) can be computed in computably-bounded time by a Turing machine with oracle $\Gamma_{\mathrm{BB}}$ unless it's already computable (without oracle), right? But $\Gamma_{\mathrm{BB}}$ itself looks like it's a counterexample: it's computable in linear time by such a machine, and it's not computable. (I've been struggling against similar contradictions for some time, so maybe I'm all confused and maybe this is silly.) Jun 25 '20 at 13:16
• What I'm using is that if your running time is computable, having gamma_BB as oracle does not allow you to compute BB(n), because the result is not within a computable range of the input. Recognizing H is therefore still impossible, because your input is "small", while recognizing Gamma_BB is possible, because your input is "big", it consists in a pair (x,v). So not all uncomputable sets are still uncomputable, only those where membership of n depends on BB(f(n)), as opposed to those where membership of n depends on membership of f(n) in Gamma_BB (f is any computable function). Jun 25 '20 at 17:31
• @Gro-Tsen I made it more explicit, let me know if something is still unclear/incorrect. Thanks for your nice question in any case ! Jul 6 '20 at 10:43
• I'm convinced! Your answer is even a bit clearer than Laurent's now, but since he provided a (partial) solution to the second question, I'm keeping his as the “approved” answer. Jul 7 '20 at 11:07
• Thanks for the edit, that is a very nice proof! I agree it is better than mine :-) Jul 11 '20 at 7:24