[FOM] Recursive but not p.r. computable functions -- the simplest "natural" examples???

[H. Enderton]

Peter Smith wrote:
>"natural" = not defined by a diagonal construction.

That point is exactly why you're having trouble!  The "real" reason
the primitive recursive functions can't exhaust the class of
calculable functions is that we can diagonalize out so easily.

Historical evidence:  Kleene says that when Church told him
Church's Thesis (1933?), Kleene didn't believe it.  He sat down
and tried to diagonalize out of the lambda-definable partial
functions.  It was his discovery that he couldn't do it that
convinced him of Church's Thesis!

My advice is to diagonalize.  (I am, however, shopping for a
spam filter that blocks the phrase "Cantor diagonal argument.")

--Herb Enderton
  hbe at math.ucla.edu