3 ms·

I don't understand what the problem is asking.

jacquesm 17y ago
The idea is to figure out how many cycles it takes before a 'beaver' halts, if at all (it is a given they should, but after how many cycles is an open problem for more than the smallest numbers of states). They have extremely simple rules, yet take a very long time before they finally do come to a halt. It's an interesting little problem, if such tremendously simple state machines can exhibit such complex behavior it gives you some indication of how hard it would be to answer those questions for more complicated state machines.
krig 17y ago
Here is a clearer explanation of the problem: http://www.logique.jussieu.fr/~michel/tmi.html 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.
gwern 17y ago
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...)
deleted 17y ago
[deleted]

The idea is to figure out how many cycles it takes before a 'beaver' halts, if at all (it is a given they should, but after how many cycles is an open problem for more than the smallest numbers of states). They have extremely simple rules, yet take a very long time before they finally do come to a halt. It's an interesting little problem, if such tremendously simple state machines can exhibit such complex behavior it gives you some indication of how hard it would be to answer those questions for more complicated state machines.

krig 17y ago

Here is a clearer explanation of the problem: http://www.logique.jussieu.fr/~michel/tmi.html 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.

gwern 17y ago

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...)

deleted 17y ago

[deleted]