Complexity relative to the graph of the Busy-Beaver function

Question

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.)

Answer 1

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}$.

Answer 2

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.

Edit: explicit proof of contradiction

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)<BB(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<N$.

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

• If $n<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<n$, 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.