Editing Busy beaver (section)

==== Non-computability ====
Radó's 1962 paper proved that if <math>f: \mathbb{N} \to \mathbb{N}</math> is any [[computable function]], then Σ(''n'') > ''f''(''n'') for all sufficiently large ''n'', and hence that Σ is not a computable function.<ref name="rado" />

Moreover, this implies that it is [[Undecidable problem|undecidable]] by a general [[algorithm]] whether an arbitrary Turing machine is a busy beaver. (Such an algorithm cannot exist, because its existence would allow Σ to be computed, which is a proven impossibility. In particular, such an algorithm could be used to construct another algorithm that would compute Σ as follows: for any given ''n'', each of the finitely many ''n''-state 2-symbol Turing machines would be tested until an ''n''-state busy beaver is found; this busy beaver machine would then be simulated to determine its score, which is by definition Σ(''n'').)

Even though Σ(''n'') is an uncomputable function, there are some small ''n'' for which it is possible to obtain its values and prove that they are correct. It is not hard to show that Σ(0) = 0, Σ(1) = 1, Σ(2) = 4, and with progressively more difficulty it can be shown that Σ(3) = 6, Σ(4) = 13 and Σ(5) = 4098 {{OEIS|A028444}}. Σ(''n'') has not yet been determined for any instance of ''n'' > 5, although lower bounds have been established (see the [[#Known results|Known values]] section below).