Re:Who Can Name the Bigger Number?
by sun_machine on Wednesday February 18, 2015 @01:12PM
(#9069992)
Here's a proof I came up with a few days ago (and it became relevant so quickly!)
Assume by contradiction that there is a computable function f that grows faster than the busy beaver problem. We can then make a Turing Machine that takes input n, calculates f(n), and then constructs and simulates every n-state Turing Machine for f(n) steps. Since f grows faster than the number of steps the most productive TM would take, any simulated machine in not in the halt state would never halt, and we could select the busiest beaver out of the remaining Turing Machines. We have constructed a TM that computes the busy beaver problem, which is a contradiction. Thus, there can be no computable function that grows faster than the busy beaver function.
Assume by contradiction that there is a computable function f that grows faster than the busy beaver problem. We can then make a Turing Machine that takes input n, calculates f(n), and then constructs and simulates every n-state Turing Machine for f(n) steps. Since f grows faster than the number of steps the most productive TM would take, any simulated machine in not in the halt state would never halt, and we could select the busiest beaver out of the remaining Turing Machines. We have constructed a TM that computes the busy beaver problem, which is a contradiction. Thus, there can be no computable function that grows faster than the busy beaver function.