8
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ 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? $\endgroup$
    – tparker
    Oct 31, 2020 at 15:37

1 Answer 1

Reset to default
36
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ I am not convinced. As far as I can see, if an algorithm has known worst case running time Θ(BB(n)) you could only use that to solve the halting problem if you can create a worst case input for a given n. $\endgroup$
    – Taemyr
    Oct 31, 2020 at 19:20
  • $\begingroup$ Also; take a terminating two symbol turing machine as input. Tag each consequtive 1 of this machines output with the position of said symbol. Iterate over pairs of positions. Running time Ω(BB(n)^2) $\endgroup$
    – Taemyr
    Oct 31, 2020 at 19:24
  • 7
    $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Oct 31, 2020 at 19:31
  • 1
    $\begingroup$ 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)$. $\endgroup$
    – Yuval Filmus
    Nov 1, 2020 at 13:23
  • 1
    $\begingroup$ 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))$. $\endgroup$
    – rus9384
    Nov 1, 2020 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.