News for hackers. Stuff that matters.
Re:The Busy Beaver Problem by gwern on Thursday October 29, 2009 @09:26AM (#909961)
It's basically asking, 'what's the biggest number a particular Turing Machine can compute?' (expressed in unary).

This is interesting as an upper bound - for example, if we have a Turing Machine and we know its Busy Beaver number _m_, we can run any of its programs and if the program fills more than _m_ while running, we know the program doesn't terminate! (Because if it did ever terminate, we would have a different Busy Beaver number, which is a contradiction.) In other words, the Busy Beaver lets us solve the Halting Problem for a specific Turing Machine; doesn't violate Turing, but is still very interesting.

As Wikipedia says, "This machine attains the limits on the amount of time and space that a halting Turing machine of the same class can consume." (This is terribly worded, so I'm going to go edit it now...)

There are no comments on this comment yet.