busy beaver is uncomputable
-
http://www.earlham.edu/~peters/courses/logsys/turing2.htm (This proof looks cool. But I think in step (3) it should be \(n+d\) rather than \(n+1\).)
-
http://cis.csuohio.edu/~somos/beaver.ps (This proof not only proves \(\Sigma (n)\), i.e., busy beaver function, is uncomputable, but also shows that \(\Sigma (n)\) grows faster than any computable function asymptotically.)
-
I think up of a proof using the recursion theorem. Suppose there is a TM \(B\) that can compute the busy beaver function, then construct a TM \(M\), starting on blank tape, do the following operation:
-
Get its own description \(<M>\), via the recursion theorem.
-
Once you know \(<M>\), you know the number of states of \(M\). Denote it by \(k\). Use \(B\) to compute the busy beaver function of \(k\).
-
Write \(k+1\) 1’s on the tape, leading to a contradiction.
-