<p>Here is a negative answer to question 1.</p>
<p>Let us assume that there is a computable function <span class="math-container">$f$</span> such that there is a Turing machine <span class="math-container">$M$</span> recognizing <span class="math-container">$H$</span> in time <span class="math-container">$f(n)$</span> with oracle <span class="math-container">$\Gamma_{BB}$</span>.
Let <span class="math-container">$g$</span> be a computable function bounding the maximal integer that <span class="math-container">$M$</span> can write on its tape on input of size <span class="math-container">$n$</span>, for instance with binary encoding <span class="math-container">$g(n)=2^{f(n)}$</span>.</p>
<p>On an input of size <span class="math-container">$n$</span>, the machine <span class="math-container">$M$</span> can only call the oracle on pairs <span class="math-container">$(x,y)$</span> with <span class="math-container">$y\leq g(n)$</span>. Since <span class="math-container">$BB$</span> is eventually bigger than <span class="math-container">$g$</span>, this would mean that there is a recursive procedure that decides the halting problem, using only the value of <span class="math-container">$BB$</span> for machines of smaller size. So using recursive calls, a finite amount of data would be enough: the values <span class="math-container">$BB(n)$</span> for <span class="math-container">$n\leq N$</span>, where <span class="math-container">$N$</span> is the threshold from where <span class="math-container">$BB$</span> is always bigger than <span class="math-container">$g$</span>.</p>
<p>This would make <span class="math-container">$H$</span> recursive, since it would be recognized by a machine with a finite oracle.</p>
<p><strong>Edit: explicit proof of contradiction</strong></p>
<p>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 <span class="math-container">$M$</span>, and a function <span class="math-container">$g$</span> as above. We take <span class="math-container">$N$</span> such that for all <span class="math-container">$n\geq N$</span>, <span class="math-container">$g(n)&lt;BB(n)$</span>.
Here is a description of an algorithm <span class="math-container">$A$</span> solving the halting problem <span class="math-container">$H$</span>.
This algorithm <span class="math-container">$A$</span> has access to a lookup table for all values <span class="math-container">$BB(k)$</span> with <span class="math-container">$k&lt;N$</span>.</p>
<p>Here is the behaviour of <span class="math-container">$A$</span> on input <span class="math-container">$\langle M_i\rangle$</span> of size <span class="math-container">$n$</span>.</p>
<ul>
<li><p>If <span class="math-container">$n&lt;N$</span>, use the lookup table to find <span class="math-container">$BB(n)$</span>, and simulate <span class="math-container">$M_i$</span> for <span class="math-container">$BB(n)+1$</span> steps, answer NO if it does not finish within this time and YES otherwise.</p>
</li>
<li><p>If <span class="math-container">$n\geq N$</span>, then simulate <span class="math-container">$M(\langle M_i\rangle)$</span>. Each time an oracle call is performed, asking for <span class="math-container">$\Gamma_{BB}(x,y)$</span>, do the following:</p>
<ul>
<li><p>If <span class="math-container">$x\geq n$</span>, have the oracle call return NO. This is correct because by choice of <span class="math-container">$N$</span>, <span class="math-container">$y$</span> is necessarily strictly smaller than <span class="math-container">$BB(x)$</span>.</p>
</li>
<li><p>If <span class="math-container">$x&lt;n$</span>, recursively call <span class="math-container">$A(\langle M' \rangle)$</span> for all machines <span class="math-container">$M'$</span> of size <span class="math-container">$x$</span>. This allows to fully simulate all machines of this size that halt, and compute the maximal running time <span class="math-container">$BB(x)$</span> among them. Comparing <span class="math-container">$BB(x)$</span> to <span class="math-container">$y$</span> allows to return the correct answer for the oracle call.</p>
</li>
</ul>
</li>
</ul>
<p>Since recursive calls are always performed on machines of smaller size, the algorithm <span class="math-container">$A$</span> always halts, and it is able to fully simulate the run of <span class="math-container">$M$</span> on <span class="math-container">$\langle M_i\rangle$</span>. So it is a correct algorithm deciding the halting problem <span class="math-container">$H$</span>, and we obtain a contradiction.</p>

CC BY-SA 4.0
2020-06-25T13:16:46.397Z
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.)
Gro-Tsen
CC BY-SA 4.0
2020-06-25T17:31:17.637Z
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).
Denis
CC BY-SA 4.0
2020-07-06T10:43:25.137Z
@Gro-Tsen I made it more explicit, let me know if something is still unclear/incorrect. Thanks for your nice question in any case !
Denis
CC BY-SA 4.0
2020-07-07T11:07:24.940Z
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.
Gro-Tsen
CC BY-SA 4.0
2020-07-11T07:24:12.907Z
Thanks for the edit, that is a very nice proof! I agree it is better than mine :-)
LaurentBienvenu
CC BY-SA 4.0
2020-06-24T18:04:24.987Z
2020-07-06T14:49:42.687Z
2020-07-06T14:49:42.687Z
Denis
<p>Really nice question(s). I don't fully follow Denis’ answer, so I'm going to try my own.</p>
<p>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 <span class="math-container">$H$</span> can be computed from oracle <span class="math-container">$\Gamma_{BB}$</span> in computably bounded time, and let <span class="math-container">$f$</span> be a computable bound.</p>
<p>First, I claim that for all <span class="math-container">$n$</span>, the first <span class="math-container">$2^{n+1}$</span> bits of <span class="math-container">$H$</span> form a string <span class="math-container">$x_n$</span> of Kolmogorov complexity at least <span class="math-container">$n$</span>. Indeed, if we knew <span class="math-container">$x_n$</span>, this would allow us to know which programs of size <span class="math-container">$\leq n$</span> halt, so we could run all of them and return a string different from all the outputs of terminating programs of size <span class="math-container">$\leq n$</span>, hence of Kolmogorov complexity <span class="math-container">$&gt;n$</span>. In other words, we can computably transform <span class="math-container">$x_n$</span> into a string of complexity <span class="math-container">$&gt;n$</span>, which by conservation of complexity implies <span class="math-container">$K(x_n)&gt;n$</span> (I ommit the usual additive constant).</p>
<p>On the other hand, by our assumption the first <span class="math-container">$2^{n+1}$</span> bits of <span class="math-container">$H$</span> can be computably obtained from the first <span class="math-container">$f(2^{n+1})$</span> bits of <span class="math-container">$\Gamma_{BB}$</span>. But <span class="math-container">$\Gamma_{BB}$</span> is very, very, sparse hence in particular, for infinitely many <span class="math-container">$n$</span>, the string <span class="math-container">$y_n$</span> consisting of the first <span class="math-container">$f(2^{n+1})$</span> bits of <span class="math-container">$\Gamma_{BB}$</span> is all zeroes except perhaps for the the first, say, <span class="math-container">$n/2$</span> bits, and thus <span class="math-container">$y_n$</span> must have Kolmogorov complexity less than <span class="math-container">$n/2$</span> (it suffices to specify the first <span class="math-container">$n/2$</span> bits), which contradicts the fact that the first <span class="math-container">$2^{n+1}$</span> bits of <span class="math-container">$H$</span> can be computably obtained from <span class="math-container">$y_n$</span>.</p>
<p>Question 2 goes right into current research in computability theory. Fortnow proposed a little while ago the concept of `low for speed’. An oracle <span class="math-container">$X$</span> is low for speed if it does not alter any computational complexity class. More precisely, <span class="math-container">$X$</span> is low for speed if any computable language <span class="math-container">$L$</span>  that can be computed from oracle <span class="math-container">$X$</span> in time <span class="math-container">$f$</span> can be computed without <span class="math-container">$X$</span> in time <span class="math-container">$poly(f)$</span>. While we do not have a full characterization of low for speed oracles, we know that:</p>
<ul>
<li>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)</li>
<li>that they form a measure 0 set (Bienvenu Downey, <a href="https://arxiv.org/abs/1712.09710" rel="noreferrer">https://arxiv.org/abs/1712.09710</a>) but they form a meager set if and only if <span class="math-container">$P \not= NP$</span> (Bayer, ibid)</li>
<li>that lowness for speed is not a Turing degree notion, but any <span class="math-container">$X \geq_T \emptyset’$</span> is not low for speed (Bienvenu-Downey, ibid)</li>
</ul>
<p>From this last point, we know that <span class="math-container">$\Gamma_{BB}$</span> is not low for speed, so there is some computable language which can be computed much faster with <span class="math-container">$\Gamma_{BB}$</span> than without it. I'd have to think about it, but I believe we could cook up a language which is in <span class="math-container">$\mathbf{P}^{\Gamma_{BB}}$</span> but not in <span class="math-container">$\mathbf{P}$</span>.</p>

CC BY-SA 4.0
2020-06-26T11:58:52.710Z
2020-06-26T11:58:52.710Z
LaurentBienvenu
<p>This question is inspired by the comments made on <a href="https://cstheory.stackexchange.com/questions/47085/has-there-been-any-development-of-complexity-theory-for-other-turing-degrees-tha">this other question</a> that I asked, and by an attempt to provide an explicit example of a complexity question beyond the Turing degree <span class="math-container">$\mathbf{0}$</span>.  (And like the former question, I'm not sure whether this is more appropriate here or on MathOverflow.)</p>
<p>Let <span class="math-container">$\Gamma_{\mathrm{BB}}$</span> be the graph of the Busy-Beaver function, i.e., <span class="math-container">$\Gamma_{\mathrm{BB}}$</span> is the set of <span class="math-container">$(n,v)$</span> such that <span class="math-container">$v = \mathrm{BB}(n)$</span> (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 <span class="math-container">$\mathrm{BB}(n)$</span> is the maximal number of <em>execution steps</em> that a Turing machine with <span class="math-container">$n$</span> states can take and eventually halt).  Now consider Turing machines with <span class="math-container">$\Gamma_{\mathrm{BB}}$</span> as an oracle: i.e., they are allowed to ask the question “is <span class="math-container">$v = \mathrm{BB}(n)$</span>?” at any point in their computation.</p>
<p>Since <span class="math-container">$\mathrm{BB}$</span> is in the same Turing degree <span class="math-container">$\mathbf{0}'$</span> as the halting problem <span class="math-container">$H$</span>, such machines can indeed solve the halting problem (given a machine <span class="math-container">$e$</span> having <span class="math-container">$n$</span> states, simulate its execution while, at each step <span class="math-container">$v$</span>, asking <span class="math-container">$\Gamma_{\mathrm{BB}}$</span> whether <span class="math-container">$v = \mathrm{BB}(n)$</span>, and stop whenever either the machine stops or we know we've run more steps than a machine with <span class="math-container">$n$</span> steps can possibly go through).</p>
<p>Now I am interested in the time complexity for such machines with <span class="math-container">$\Gamma_{\mathrm{BB}}$</span> as an oracle: clearly the algorithm I described has an enormous complexity (comparable to <span class="math-container">$\mathrm{BB}$</span> itself!).  So I am inclined to ask whether one can do better.</p>
<p>Specifically:</p>
<blockquote>
<p><strong>Question 1:</strong> Does the halting problem <span class="math-container">$H$</span> belong to any standard complexity class relativized to the <span class="math-container">$\Gamma_{\mathrm{BB}}$</span> oracle, like <span class="math-container">$\mathbf{P}^{\Gamma_{\mathrm{BB}}}$</span> (polynomial time), <span class="math-container">$\mathbf{EXP}^{\Gamma_{\mathrm{BB}}}$</span> (exponential time) or <span class="math-container">$\mathbf{PR}^{\Gamma_{\mathrm{BB}}}$</span> (primitive recursive in <span class="math-container">$\Gamma_{\mathrm{BB}}$</span>)?</p>
</blockquote>
<p>Note in particular that, if such is the case, once we can compute the halting problem, we can compute <em>all</em> computable sets in the same complexity (I mean, if <span class="math-container">$H$</span> is the halting problem, and <span class="math-container">$\mathbf{R}$</span> is the class of all computable sets, we have <span class="math-container">$\mathbf{R} \subseteq \mathbf{P}^H$</span> by letting the oracle do all the computational work, so a positive answer to question 1, say, for <span class="math-container">$\mathbf{P}$</span>, would imply that <span class="math-container">$\mathbf{R} \subseteq \mathbf{P}^{\Gamma_{\mathrm{BB}}}$</span>).</p>
<blockquote>
<p><strong>Question 2:</strong> Or, at the other extreme, is it perhaps true that <span class="math-container">$\mathbf{P}^{\Gamma_{\mathrm{BB}}} \cap \mathbf{R}$</span> (functions computable in polynomial time with <span class="math-container">$\Gamma_{\mathrm{BB}}$</span> as oracle, and which happen to also be computable without oracle) equals <span class="math-container">$\mathbf{P}$</span>, i.e., that having access to <span class="math-container">$\Gamma_{\mathrm{BB}}$</span> as an oracle won't speed up the computation of any problem that's already computable?  (Or replace <span class="math-container">$\mathbf{P}$</span> by any standard complexity class like the ones mentioned in the previous question.)</p>
</blockquote>

<cc.complexity-theory><computability>
Complexity relative to the graph of the Busy-Beaver function
Gro-Tsen
# Complexity relative to the graph of the Busy-Beaver function

(Asked by: username_0 on 2020-06-23)

This question is inspired by the comments made on [this other question](https://cstheory.stackexchange.com/questions/47085/has-there-been-any-development-of-complexity-theory-for-other-turing-degrees-tha) 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.)

**Tags:** cc.complexity-theory, computability

---

## 2 answers

### Answer by username_2 on 2020-06-26. Score: 6 | Accepted answer

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 by username_1 on 2020-06-24. Score: 5

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

> **Comments:**
> **username_0**: 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.)  
> **username_1**: 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).  
> **username_1**: @Gro-Tsen I made it more explicit, let me know if something is still unclear/incorrect. Thanks for your nice question in any case !  
> **username_0**: 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.  
> **username_2**: Thanks for the edit, that is a very nice proof! I agree it is better than mine :-)  

---

