[FOM] Parson's Thesis? [A primitive recursive analogue ...]

[H. Enderton]

Rex Butler wrote:
>1.  What can be said about the canonical nature of the primitive
>recursive functions? ...  Are there other seemingly canonical
>classes of provably recursive functions?

A good question.  Is there any inherent significance to the class
of primitive recursive functions, or is it merely a convenient
class of total recursive functions with the property of having
recognizably total descriptions?  (The class of all total recursive
functions lacks this property, so *something* is needed.)

One piece of evidence for inherent signifance is the theorem
by Parsons you cite (being the provably total functions in
I-Sigma_1).  Another is the fact that the primitive recursive
functions are exactly the ones having programs without "go to"
commands.  (For a precise version, see Chapter 13 in the textbook
by Davis and Weyuker.  For some reason, this chapter was dropped
in the second edition.)  Of course, this characterization has
more a computer science flavor than a foundational one.

But a competing class consists of the (Kalmar) elementary functions.
A smaller class, it also has claims to inherent significance.
A 1963 paper by Robert Ritchie shows that these are exactly the
functions for which the running time is predictable (this concept
requires an iterative definition).  See the review JSL XXVIII 252.
Again, this might get a computer science classification.

Perhaps others can point out evidence in favor of assigning
"canonical nature" to one or the other of these classes -- or
to other candidates.

--Herb Enderton