Hungarian mathematician Tibor Rado invented the Busy Beaver Problem: given a halting Turing machine, how many “1s” can it write before it halts? If the Turing machine in question has n states, this number is denoted S(n) and grows faster than any computable function f(n). If the Turing machine has 4 states, it writes 13 ones; if it has 5 states, it writes at least 4098 ones (Buntrock-Marxen beaver, 1989); if it has 6 states, it writes an enormous number of ones, not yet calculated but certainly > 4096^4096 (M.W. Green’s Theorem, 1964).
