Chapter 13.5, Problem 32E

Show that the function B(n) cannot be computed by any Turing machine. [Hint: Assume that there is a Turing machine that computes B(n) in binary. Build a Turing machine T that, starting with a blank tape, writes n down in binary, computes B(n) in binary and converts B(n) from binary to unary. Show that for sufficiently large n, the number of states of T is less than B(n), leading to a contradiction.)