Follow Up: The Busy Beaver Function
Why can there be no computable bound to the Busy Beaver Function?
Before we get into things, we have to be sure to define what we mean by a program or procedure— what specific language or rules or model we are using. But once we’ve done that, all the arguments will be just exactly the same:
We can list out all the programs (in our language or rules or model) in some procedural way. (For example, just start building longer and longer programs up systematically.) Now some of these will run forever and some of these will eventually stop.
We know, because the Halting Problem is not a computable question, that there is no procedure than can tell us whether the Nth program will eventually halt or run forever.
(Sure, one procedure is just to run the Nth program; if the program halts, we’ll eventually learn this. But if it hasn’t halted after a long time, we won’t know if the program is going to run forever, or another century, or just another minute. We won’t know a thing. There is no procedure that will tell us, in a finite amount of time, whether a given arbitrary program will run forever or halt.)
Let’s define a function: B(n). On our list of programs, among the programs that actually do eventually halt (whichever ones they are), how many steps does it take before the nth halting program halts?
Now B(n) cannot be bounded by any function that can be computed! Not n2, nor 2n nor n^n^n^n nor ….
B(n) has to pop above any computable function!!!
I don’t know about you, but this just blows my mind.
Here’s the argument:
Suppose there were a function f(n) that can be computed such that f(n)>B(n) for all n. Now consider the Nth program. We don’t know whether or not this program halts. If it does though, it will be the nth halting program for some n < = N and so will take fewer than f(n) steps to halt.
In other words, if we run our program for more than f(n) steps, for any possible n< =N, we know we are in the clear and the program will run forever.
But this gives us a procedure for figuring out whether any given program halts or not. If you have the Nth program, calculate f(1), f(2), … f(N) and take the biggest of those values.
(Remember, the assumption was that we can compute these values of f!) Lets call that maximum value F.
Run the program for F steps if you can. If you make it all the way to F steps without halting, you know the program will never halt (remember we are assuming B(n) < f(n) for all n).
So, we have a procedure to determine whether or not an arbitrary program halts or not. What went wrong? Our assumption, that there could be a computable bound f(n) for B(n) just could not be so: B(n) must not be bounded by any computable function!
The classical busy beaver problem, posed by T. Rado, is a little different. But only because we have to fix our terms. First off, he is using straight-out plain jane Turing machines. Second, he asks: among the (finite collection of) Turing machines with N states and M symbols, some halt and some do not. Among those that do halt, which one takes the very longest to do so? He calls this the N-state, M-symbol busy beaver. Generally speaking, we will never know what the busy beaver for a given N and M are. But there are some astounding candidates that have been discovered!
The functions Rado considered were just a little different than the B we defined above, but they also have no computable bound and the proof is just the same. Rado defines S(N,M) to be absolute maximum number of steps taken by a halting N state M symbol turing machine.
The Math Factor in iTunes
RSS feed
Comments RSS
mathbun.com
Ikosarakt said,
December 21, 2012 at 6:01 am
BB(2n), however, might be lower-bounded by 3{n-2}3, where a{c}b means a^^^…^^^b (with c up-arrows).