1. 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\).)

  2. 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.)

  3. 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.