patternCritical
Is busy beaver the fastest growing function known to man?
Viewed 0 times
thebeaverfunctionbusygrowingfastestknownman
Problem
I just had this interesting question. What is the fastest growing function known to man? Is it busy beaver?
We know functions such as $x^2$, but this function grows slower than $2^x$, which in turn grows slower than $x!$, which in turn grows slower than $x^x$. We can then combine functions, to have $(x^x)!$ that grows faster than $x^x$, and so on.
Then we arrive at recursive functions such as Ackermann's function $A(x,x)$ that grows much faster than $(x^x)!$. Then people though about busy beaver $B(x)$ function that grows even faster than Ackermann's function.
At this point I haven't heard of any other functions that grow faster than busy beaver. Does it mean that there are no other functions that can possibly grow quicker than busy beaver? (Aside from factorial of $B(x)$ and like $A(B(x), B(x))$, etc.)
We know functions such as $x^2$, but this function grows slower than $2^x$, which in turn grows slower than $x!$, which in turn grows slower than $x^x$. We can then combine functions, to have $(x^x)!$ that grows faster than $x^x$, and so on.
Then we arrive at recursive functions such as Ackermann's function $A(x,x)$ that grows much faster than $(x^x)!$. Then people though about busy beaver $B(x)$ function that grows even faster than Ackermann's function.
At this point I haven't heard of any other functions that grow faster than busy beaver. Does it mean that there are no other functions that can possibly grow quicker than busy beaver? (Aside from factorial of $B(x)$ and like $A(B(x), B(x))$, etc.)
Solution
The busy beaver function grows faster than any computable function. However, it can be computed by a Turing machine which has been given access to an oracle for solving the halting problem. You can then define a "second order" busy beaver function, that grows faster than any function that can be computed even by any Turing machine with an oracle for the halting problem. You can keep doing this forever, building up a hierarchy of ever faster growing busy beaver functions.
See Scott Aaronson's excellent essay on this topic, Who Can Name the Bigger Number?.
See Scott Aaronson's excellent essay on this topic, Who Can Name the Bigger Number?.
Context
StackExchange Computer Science Q#4678, answer score: 51
Revisions (0)
No revisions yet.