Let me tell you a story about how I (and my dad) first got into the Busy Beaver game:| sligocki
The quest to find the longest-running simple computer program has identified a new champion. It’s physically impossible to write out the numbers involved using standard mathematical notation.| Quanta Magazine
After decades of uncertainty, a motley team of programmers has proved precisely how complicated simple computer programs can get.| Quanta Magazine
An n-instruction Turing machine is a Turing machine having an arbitrary number of states and symbols, but having only n defined transitions/instructions in its transition table (all others are undefined).| wiki.bbchallenge.org
The 2-state, 5-symbol Busy Beaver problem, BB(2,5), is unsolved. With the discovery of the Cryptid machine Hydra in April 2024, we now know that we must solve a Collatz-like problem in order to solve BB(2,5) and thus BB(2,5) is Hard.| wiki.bbchallenge.org
Turing machine programs are sometimes represented as directed graphs. The vertices of the graph are the program’s states and the edges are transitions between states. The program’s print and shift instructions are relegated to being labels for the edges. Here’s an example:| Something Something Programming
The aim of the Busy Beaver game is to find the longest running Turing machine program of n states and k colors. Busy Beaver programs could in principle be written by hand, but nobody has ever succeeded in doing so. Instead, these programs are discovered through exhaustive search. This is done by a two-stage process:| Something Something Programming
