Busy beaver

The busy beaver function Sigma(n), introduced by Tibor Radó in 1962, asks: what is the maximum number of steps that an n-state Turing machine can perform before halting, starting from a blank tape? This function grows faster than any computable function — it is itself uncomputable, because computing it would require solving the halting problem. For small n, exact values are known: Sigma(5) = 47,176,870 and Sigma(6) is known to exceed 10^36534. Beyond these small values, the function is not merely unknown but unknowable by any algorithmic procedure.

The busy beaver function serves as a concrete demonstration that undecidability is not an abstract concern about exotic programs. Even a six-state Turing machine — simple enough to describe in a paragraph — has behavior that no algorithm can fully characterize. The function connects the theory of computation to Kolmogorov complexity: the values of Sigma(n) encode the solution to the halting problem for n-state machines, making them maximally complex in an algorithmic sense.