Great Beaver Breakthroughs
This summer, a team of enthusiastic amateurs solved one of the biggest open questions in computer science by I found the fifth beaver busy. Named after a type of computer program that is particularly laborious and time-consuming to run, the problem relates to some of the most profound open questions in computer science and mathematics.
The problem involves Turing machines, some of the simplest computing devices possible, first designed by Alan Turing as a model for a general computer and now easily simulated online. Depending on their initial settings, these can run indefinitely or stop after a set number of steps. The busy beaver problem asks: Given only a certain number of rules governing the machine, how long can it run, not forever? Researchers solved this problem for machines with 1, 2, 3, or 4 rules (1, 6, 21, and 107 steps, respectively), but the fifth busy beaver number eluded them for decades.
Quanta editor Ben Brubaker chronic the efforts of a global team, made up mostly of non-experts, to find the number – it’s 47,176,870 – and prove it couldn’t be higher. The problem has no direct application, but finding the solution represents a kind of victory over overwhelming mathematical complexity – a case that early research from the sixth busy beaver suggests we may never see again.
And in January, we talked about another diverse team of non-professionals who helped solve a different kind of digital puzzle. This effort focused on the game of lifeby John Conway, and the search for repeating patterns of specific lengths. By finding patterns that repeated after 19 and 41 steps, they proved that the Game of Life is “omniperiodic” – able to repeat after every possible number of steps.