News for hackers. Stuff that matters.
Re:The Busy Beaver Problem by krig on Thursday October 29, 2009 @09:25AM (#909959)
Here is a clearer explanation of the problem: http://www.logique.jussieu.fr/~michel/tmi.html

My attempt at explaining it (I'm not sure I've understood it completely, though): Busy Beavers are Turing machines that eventually reach a halting state. The goal is to find the busy beaver, for a given number of states, that takes the longest to do so. This turns out to be a tricky problem for states >= 5. That is, there are solutions to n=5,..., but no one has formally proved that there isn't a busy beaver that will take longer to halt.

There are no comments on this comment yet.