That’s why finding busy beavers is so hard. None of these are the busy beaver, but how do you definitively rule them out? Turing proved that there’s no way to automatically tell whether a machine that runs for a thousand or a million steps won’t eventually terminate. Of 6,561 possible machines with two rules, the one that runs the longest - six steps - before halting is the busy beaver. The busy beaver number of a one-rule machine, or BB(1), is therefore 1.īut adding just a few more rules instantly blows up the number of machines to consider. The busy beaver game asks: Given a certain number of rules, what’s the maximum number of steps that a Turing machine can take before halting?įor instance, if you’re only allowed one rule, and you want to ensure that the Turing machine halts, you’re forced to include the halt instruction right away. But he also proved that there’s no reliable, repeatable method for distinguishing machines that halt from machines that simply run forever - a fact known as the halting problem. Some rules say to jump back to previous rules eventually there’s a rule containing an instruction to “halt.” Turing proved that this simple kind of computer is capable of performing any possible calculation, given the right instructions and enough time.Īs Turing noted in 1936, in order to compute something, a Turing machine must eventually halt - it can’t get trapped in an infinite loop. If the square contains a 1, leave the 1, move one square to the left and consult rule 3.Įach rule has this forking choose-your-own-adventure style. If the square contains a 0, replace it with a 1, move one square to the right and consult rule 2. A Turing machine performs actions on an endless strip of tape divided into squares. The busy beaver game is all about the behavior of Turing machines - the primitive, idealized computers conceived by Alan Turing in 1936. But the busy beaver game can show where it actually lies on a number line, like an ancient map depicting the edge of the world. The logician Kurt Gödel proved the existence of such mathematical terra incognita nearly a century ago. It even offers a glimpse of where the logical bedrock underlying math breaks down. According to researchers, the busy beaver game provides a concrete benchmark for evaluating the difficulty of certain problems, such as the unsolved Goldbach conjecture and Riemann hypothesis. The recent work suggests that the search for long-running computer programs can illuminate the state of mathematical knowledge, and even tell us what’s knowable. “In math, there is a very permeable boundary between what’s an amusing recreation and what is actually important,” said Scott Aaronson, a theoretical computer scientist at the University of Texas, Austin who recently published a survey of progress in “BusyBeaverology.”
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |