News for hackers. Stuff that matters.
Re:The Busy Beaver Problem by rw on Thursday October 29, 2009 @09:26AM (#909960)
This problem is what originally got me interested in computational complexity. Everybody knows about the halting problem; but the Busy Beaver, now that's a clever and weird idea! The growth rate of Sigma(n) is ridiculous. Studying this illuminated just how vast a problem-space can be (especially concerning the lack of knowledge we have by knowing a particular machine's configuration: we don't learn much by inspection, we just have to run the damn thing). I see the Busy Beaver "competition" as our more-interesting equivalent to searching for large primes.

There are no comments on this comment yet.