12
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

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

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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.) $\endgroup$ – Gro-Tsen Jun 25 at 13:16
  • $\begingroup$ 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). $\endgroup$ – Denis Jun 25 at 17:31
  • $\begingroup$ @Gro-Tsen I made it more explicit, let me know if something is still unclear/incorrect. Thanks for your nice question in any case ! $\endgroup$ – Denis Jul 6 at 10:43
  • $\begingroup$ 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. $\endgroup$ – Gro-Tsen Jul 7 at 11:07
  • $\begingroup$ Thanks for the edit, that is a very nice proof! I agree it is better than mine :-) $\endgroup$ – LaurentBienvenu Jul 11 at 7:24

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.