Re:The Busy Beaver Problem
by jacquesm on Thursday October 29, 2009 @09:19AM
(#909951)
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.
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.