The Busy Beaver function
Let Σ be a finite alphabet, for instance {0, 1}; let M be the set of Turing machines with alphabet Σ, and let H ⊆ M be the set of Turing machines that halt when given the empty string ε as input.
For each M ∈ H, Let s(M) be the number of steps performed by M before halting (when given ε as input).
Finally, let S : ℕ → ℕ be the function defined by
S(n) = max {s(M) : M ∈ H and M has n states}
Notice that S is well-defined, since only finitely many Turing machines with n states exist.
In other words, S(n) is the maximum number of steps performed on ε among all halting Turing machines with n states. S is called the Busy Beaver function.
It turns out that S is uncomputable because it grows faster than any computable function, that is, for all recursive functions f : ℕ → ℕ we have S(n) > f(n) for large enough n, and in particular f is o(S).
