6
$\begingroup$

The busy beaver function $BB$ asymptotically bounds any computable function. It is easy to show that there are lower bounds, for example, $log(BB)$.

Is there a function $f$ that asymptotically bounds all computable functions, so that $BB$ is not computable even by a machine with an oracle to $f$? (obviously, $f$ has to be lower than $BB$)

$\endgroup$
3
$\begingroup$

Yes.

The Busy Beaver function has Turing degree $0'$: if I know $BB$, I can tell whether a given Turing machine will halt.

A function dominating every total computable function, meanwhile, can be constructed by any high Turing degree (this is Martin's domination theorem), and there are high degrees strictly $<_T0'$ (this was first proved by Friedberg I believe; Sacks constructed a c.e. high degree below $0'$, but that's not needed here).


So how do we build such a function? WARNING: This is pretty technical.

EDIT: To clarify, what's going on below is the construction of an $f$ which bounds all computable functions but doesn't compute $BB$. This is not the same as a high degree $<_T0'$, and indeed that's a bit more complicated to construct - the difference is that the construction below is not actually $0'$-effective.

A condition is a pair $(p, S)$ where

  • $p$ is a map from some finite set $\{0, 1, . . . , n\}$ to $\mathbb{N}$,

  • $S$ is a finite set of naturals, and

  • each $e\in S$ is the index of a total computable function.

We say $(p, S)$ extends $(q, T)$ - and write $(p, S)\le (q, T)$ (no, that's not a typo - this notation can seem confusing at first, but there's a good reason for it) - if $p$ extends $q$, $S$ contains $T$, and for each $n\in dom(p)\setminus dom(q)$ and $e\in T$, $p(n)>\varphi_e(n)$.

We'll build a sequence of conditions $(p_i, S_i)$ such that

  • $(p_0, S_0)\ge(p_1, S_1)\ge(p_2, S_2)\ge...$,

  • $dom(p_i)\supseteq \{0, 1, . . . , i\}$, and

  • $e_i\in S_i$ where $e_i$ is the $i$th index for a total computable function.

These properties ensure that the function $$f=\bigcup p_i$$ is in fact a function from $\mathbb{N}$ to $\mathbb{N}$, which dominates all computable functions.

Additionally, we'll ensure that $\Phi_e^f\not=BB$ for any $e$. This is the tricky part.

We begin the construction with $p_0=\emptyset$, $S_0=\emptyset$, and proceed inductively. Let's say we've defined $(p_n, S_n)$.

Now we ask:

Is there some $k\in\mathbb{N}$ and some finite map $q$ with domain strictly larger than that of $p_n$ such that $(q, S_n)\le (p_n, S_n)$ but $\Phi_n^q(k)\downarrow\not=BB(k)$?

If yes: Let $p_{n+1}=q$, $S_{n+1}=S_n\cup\{t_n\}$ (where $\{t_i: i\in\mathbb{N}\}$ is the set of indices of total computable functions).

If no: Let $p_{n+1}$ be any finite partial map such that $(p_{n+1}, S_n)\le (p_n, S_n)$, and let $S_n=S_n\cup\{t_n\}$.

It's now a fun exercise to show that this works! HINT: in the "no" case, it looks like we're essentially doing nothing at all. That's correct! Think about why this isn't going to be a problem . . .

$\endgroup$

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.