9
$\begingroup$

Let $BB(n)$ denote busy beaver function. It's well known that $BB(n)$ dominates all computable functions (I'm quite certain it includes partial computable functions too). However, I was wondering if we can show similar domination over functions computable from some fixed oracle $A$. In particular, I have been wondering, is it the case that:

If $A$ has low r.e. Turing degree (i.e. $A'\equiv_T 0'$), then $BB(n)$ dominates all functions computable from $A$?

Best I was able to show is that no $A$-computable function can dominate $BB(n)$ (this is quite simple, because if we can bound $BB$, then we can solve halting problem and compute $0'$).

On the other extreme, I know that there exist uncomputable degrees for which the conclusion holds (e.g. hyperimmune-free degrees, because all functions computable from it are dominated by computable functions). However, if we restrict our degrees to be recursively enumerable, I don't know the answer, so a lot simpler version of my question is:

Is there an uncomputable r.e. Turing degree such that $BB(n)$ dominates all functions computable from $A$?

I expect the answer to this last question to be "yes".

Thanks in advance.

$\endgroup$
8
$\begingroup$

It turns out you're asking about the Array Nonrecursive degrees. A degree $\mathbf{a}$ is called Array Nonrecursive (ANR) if for every function $f$ wtt-below $\emptyset'$, there is an $\mathbf{a}$-computable function $g$ which is not dominated by $f$. You don't need to consider every $f \leq_\text{wtt} \emptyset'$, though; it's enough to consider the modulus function for $\emptyset'$.

Now note that $BB \leq_{wtt} \emptyset'$, since we can compute $BB(n)$ after checking which machines with $n$ states halt on the empty input. So every ANR degree computes a function which infinitely often exceeds $BB$.

On the other hand, given a Turing machine $T$, we can effectively construct a 2-symbol machine that simulates $T$ and, if $T$ ever halts, writes in unary on the tape the number of steps $T$ performed. If $T$ has Gödel number $n$, let $h(n)$ be the number of states in this simulating machine. We can assume that $h$ is a strictly increasing function, by padding. Then if $T$ converges, it does so in at most $BB(h(n))$ steps. This means $BB(h(n))$ is greater than the modulus of $\emptyset'(n)$.

Now, suppose $\mathbf{a}$ computes a function $g$ which infinitely exceeds $BB$. Assume that $g$ is non-decreasing. Then define $f(n) = g(h(n+1))$. This is an $\mathbf{a}$-computable function. For any $g(x) > BB(x)$, fix the least $n$ with $h(n+1) > x$. Then $f(n) = g(h(n+1)) \ge g(x) > BB(x) \ge BB(h(n))$, so $f(n)$ is greater than the modulus of $\emptyset'(n)$. Thus $\mathbf{a}$ is ANR.

So the answer to your first question is no, because there are low, r.e., ANR degrees. On the other hand, there are noncomputable r.e. degrees which are not ANR, so the answer to your second question is yes.

Edit: Here's why it's enough to escape the modulus function of $\emptyset'$. Suppose $g$ infinitely often exceeds the modulus function. Assume $g$ is nondecreasing. Fix $f \leq_\text{wtt} \emptyset'$. Let $h$ be computable such that the use of $f(n)$ is bounded by $h(n)$ (here using the definition of wtt-reduction). Assume also that $h$ is nondecreasing. Let $m$ be the modulus of $\emptyset'$. Then for every $x$ with $g(x) > m(x)$, let $n$ be least such that $h(n+1) \ge x$. Then $g(h(n+1)) \ge g(x) > m(x) \ge m(h(n))$. So $t(n) = g(h(n+1))$ infinitely often exceeds $m(h(n))$, and $t$ is computable from $g$.

Now we can define a new function $u$ from $t$ as follows: on input $n$, try to compute $f(n)$ using $\emptyset'_{t(n)}\!\!\upharpoonright_{h(n)}$ in place of the oracle for $\emptyset'$ until one of two things happen: we see our guess for $f(n)$ converge, or we see $t(n) < m(h(n))$. In the first case, output our guess for $f(n)+1$. In the second case, output 0. For any $n$ with $t(n) > m(h(n))$, we will see convergence and our guess will be the true value of $f(n)$, so $u(n) = f(n)+1$. Thus $u$ infinitely often exceeds $f$, and $u$ is computable from $t$ which is computable from $g$.

$\endgroup$
  • $\begingroup$ Can you give the largest context or the subject in which one studies this? Do you have atextbook/review/lecture-note reference for this? $\endgroup$ – Anirbit Nov 26 '14 at 17:40
  • $\begingroup$ It's interesting how for every type of degree I can think of there already exists a name for it :) Thanks a lot. $\endgroup$ – Wojowu Nov 26 '14 at 17:51
  • $\begingroup$ Could you elaborate a bit, or give a reference, on why we only need to verify the fact for modulus of $\emptyset'$? I thought that I'd be able to figure that out myself, but I cannot. $\endgroup$ – Wojowu Nov 26 '14 at 18:23
  • $\begingroup$ @Anirbit, this is part of degree theory, part of recursion theory. ANR is an example of a highness notion; a degree needs to have a certain amount of computational power. I believe ANR is covered in Downey & Hirschfeldt, but I don't have my copy at hand to check. $\endgroup$ – Dan Turetsky Nov 26 '14 at 18:37
  • $\begingroup$ @Wojowu, there's probably a reference in Downey & Hirschfeldt, but I'll edit in an explanation. $\endgroup$ – Dan Turetsky Nov 26 '14 at 18:40

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.