# Are there any functions with Big O (Busy Beaver(n))?

So, I was reading this article by Scott Aaronson on big numbers, and he mentioned that the Busy Beaver sequence increases faster than all sequences computable by Turing Machines. Faster than exponentials, faster than the Aaronson sequence, and faster than a recursive use of Knuth's up-arrow notation.

This led me to a thought: are there any algorithms that grow in size with Big O (Busy Beaver(n)), aside from the Halting Problem? Is it even possible to design such an algorithm on that would run on a Turing Machine-equivalent computer?

• The title of your question asks about "functions", but the body asks about "algorithms." Which one are you asking about? There are certainly many functions that grow faster than the BB sequence. Also, are you sure that you mean to use big $O$ and not $\omega$ or another asymptotic relation? Oct 31, 2020 at 15:37

The usual meaning of algorithm is a program that always halts. Under this definition, no algorithm has a running time of $$\Theta(\mathit{BB}(n))$$, or indeed $$\Omega(\mathit{BB}(n))$$. Indeed, such an algorithm could be used to solve the halting problem (assuming you knew a constant $$c>0$$ such that the running time is at least $$c\mathit{BB}(n)$$), since you could use the algorithm to get an upper bound on $$\mathit{BB}(n)$$.
On the other hand, any algorithm has a running time of $$O(\mathit{BB}(n))$$, precisely because the busy beaver function grows faster than any computable function.
• Given a Turing machine having $n$ states, run the algorithm to get an upper bound $U(n)$ on $\mathit{BB}(n)$, then simulate the Turing machine for $U(n)$ steps. If it doesn't halt, it will never halt. Oct 31, 2020 at 19:31
• If you can compute $\mathit{BB}(n)$ you can solve the halting problem, and conversely, if you can solve the halting problem then you can compute $\mathit{BB}(n)$. Nov 1, 2020 at 13:23
• Yes, but a positive halting problem instance can be verified in finite time. There are problems that can't be and therefore their runtime would just be $\infty$, i.e. bigger than $BB(n)$. I think that'd count as $\Omega(BB(n))$. Nov 1, 2020 at 13:32