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 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&gt;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.