The Quest to Find the Longest-Running Simple Computer Program

The Busy Beaver Challenge, a notoriously difficult question in theoretical computer science, is now producing answers so large they're impossible to write out using standard mathematical notation.

The original version of this story appeared in Quanta Magazine.

Imagine that someone gives you a list of five numbers: 1, 6, 21, 107 and—wait for it—47,176,870. Can you guess what comes next?

If you’re stumped, you’re not alone. These are the first five busy beaver numbers. They form a sequence that’s intimately tied to one of the most notoriously difficult questions in theoretical computer science. Determining the values of busy beaver numbers is a daunting challenge that has attracted a cult following among both professional and amateur mathematicians for over 60 years.

Researchers identified the first four busy beaver numbers in the 1960s and 1970s. The conspicuously larger fifth ...