The fifth “Busy Beaver” number. Alan Turing proved in the early days of computing that it is impossible to determine just from the instructions of a program whether that program will run forever in an infinite loop or halt. This “halting problem” led in 1962 to a Hungarian mathematician, Tibor Radó, setting a puzzle: Finding the longest-running non-infinite program with one, two, or more rules, the “Busy Beaver” number. BB(1) is 1. BB(2) is 6. BB(3) was eventually shown to be 21. Then it got harder: A US mathematician, Allen Brady, found BB(4), 107, in 1983. Mathematicians suggested in 1990 that BB(5) would be 47,176,870, but have only now proved it — sadly, shortly after Brady died, the quantum scientist Scott Aaronson noted. |