Editing Busy beaver (section)

===Proof for uncomputability of ''S''(''n'') and Σ(''n'')===
{{Unreferenced|section|date=July 2024}}
Suppose that ''S''(''n'') is a computable function and let ''EvalS'' denote a TM, evaluating ''S''(''n''). Given a tape with ''n'' 1s it will produce ''S''(''n'') 1s on the tape and then halt. Let ''Clean'' denote a Turing machine cleaning the sequence of 1s initially written on the tape. Let ''Double'' denote a Turing machine evaluating function ''n'' + ''n''. Given a tape with ''n'' 1s it will produce 2''n'' 1s on the tape and then halt. 
Let us create the composition ''Double'' | ''EvalS'' | ''Clean'' and let ''n''<sub>0</sub> be the number of states of this machine. Let ''Create_n<sub>0</sub>'' denote a Turing machine creating ''n''<sub>0</sub> 1s on an initially blank tape. This machine may be constructed in a trivial manner to have ''n''<sub>0</sub> states (the state ''i'' writes 1, moves the head right and switches to state ''i'' + 1, except the state ''n''<sub>0</sub>, which halts). Let ''N'' denote the sum ''n''<sub>0</sub> + ''n''<sub>0</sub>.

Let ''BadS'' denote the composition ''Create_n<sub>0</sub>'' | ''Double'' | ''EvalS'' | ''Clean''. Notice that this machine has ''N'' states. Starting with an initially blank tape it first creates a sequence of ''n''<sub>0</sub> 1s and then doubles it, producing a sequence of ''N'' 1s. Then ''BadS'' will produce ''S''(''N'') 1s on tape, and at last it will clear all 1s and then halt. But the phase of cleaning will continue at least ''S''(''N'') steps, so the time of working of ''BadS'' is strictly greater than ''S''(''N''), which contradicts to the definition of the function ''S''(''n'').

The uncomputability of Σ(''n'') may be proved in a similar way. In the above proof, one must exchange the machine ''EvalS'' with ''EvalΣ'' and ''Clean'' with ''Increment'' — a simple TM, searching for a first 0 on the tape and replacing it with 1.

The uncomputability of ''S''(''n'') can also be established by reference to the blank tape halting problem. The blank tape halting problem is the problem of deciding for any Turing machine whether or not it will halt when started on an empty tape.  The blank tape halting problem is equivalent to the standard [[halting problem]] and so it is also uncomputable.  If ''S''(''n'') was computable, then we could solve the blank tape halting problem simply by running any given Turing machine with ''n'' states for ''S''(''n'') steps;  if it has still not halted, it never will.  So, since the blank tape halting problem is not computable, it follows that ''S''(''n'') must likewise be uncomputable.