Busy beaver. The busy beaver function BB(n) is defined to be the maximal number of 1s that an n-state Turing machine over the binary alphabet can leave on an initially blank tape, while still halting....

Busy beaver. The busy beaver function BB(n) is defined to be the maximal number of 1s that an n-state Turing machine over the binary alphabet can leave on an initially blank tape, while still halting. Show that BB(n) is not computable. Hint: First show how to simulate an n-state Turing machine on an input of size m by running an (m + n)-state Turing machine on an initially empty input. Then, run the (m + n)-state Turing machine for BB(m + n + 1) steps.