Proof that not every computable function over the natural numbers can be described using structural recursion.

Question

I'm reading Bird's Algebra of programming (excelent book so far). It says

It is a fact that not every computable function over the natural numbers can be described using structural recursion

I think the most reasonable way to do that is assume the negation, that is, "every computable function over the natural numbers can be described using structural recursion" and then find a counter-example.

The counter-example I though was the $sqrt$ function. But from here I'm stuck.

Can anyone tell me how to continue from here or other ways of prove it (assuming other ways exist)?

Answer 1

Square root isn't a function over natural numbers, unfortunately, since $\sqrt{2}$ isn't a natural...

You can prove the claim non-constructively by diagonalizing: there are uncountably many functions over the naturals, but only countably many can be built up using structural recursion.

For a constructive example, there are functions that grow "too fast" to be captured by structural recursion; the most famous of these is the Ackermann function.