2
$\begingroup$

Is there a function that grows asymptotically faster than the Busy Beaver numbers?

That is, I know that BB(n)^n grows faster than BB(n), but is there another sequence that can be shown to grow faster than BB(n) without itself referencing the busy beaver numbers in its definition?

$\endgroup$
5
$\begingroup$

Sure. You just need to define the analogue of the busy beaver numbers with respect to a strictly stronger model of computation. For example, let a super Turing machine be a Turing machine equipped with a halting oracle. Super Turing machines are strictly more powerful than Turing machines because they can solve a problem (namely the halting problem) that Turing machines can't. In particular, they can compute the Busy Beaver numbers.

Then define the super Busy Beaver numbers to be the Busy Beaver numbers of super Turing machines. Since super Turing machines can't solve the super halting problem (for the same reason that Turing machines can't solve the halting problem), super Turing machines can't compute the super Busy Beaver numbers, so they must grow much faster than the Busy Beaver numbers.

And of course you can iterate this process. You might enjoy reading Scott Aaronson's Who Can Name the Bigger Number? for more along these lines, and this MO question for an update.

$\endgroup$
  • $\begingroup$ I thought that a "super turing machine" was paradoxical? $\endgroup$ – John Gietzen May 26 '13 at 22:35
  • $\begingroup$ Why? They're perfectly well-defined mathematical objects. $\endgroup$ – Qiaochu Yuan May 27 '13 at 0:36

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.