[15] Georg Cantor proved that the total functions are not countable by introducing his famous diagonalization argument. Suppose the contrary, and count the functions in order f1, f2,...,fi,... . Define a new function g, which we shall prove to be not in this list, by g(i) =

fi(i) + 1, for all natural numbers i. By contradictory assumption, g occurs in the list, say g = fi. But by definition, g(i) = fi(i), which gives the required contradiction. Use a similar argument to prove that there are functions that are not partial computable.