[FOM] Parson's Thesis?

[Curtis Franks]

Herb Enderton wrote:
> 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?
> 
> One piece of evidence for inherent signifance 
 > [of prim. rec. functions] is the theorem
> by Parsons you cite (being the provably total functions in
> I-Sigma_1).  ... 
 > 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.

As in the case of prim. rec. functions, the CS route to motivating 
Kalmar elementary functions is one among many. Professor Enderton points 
out Ritchie's AMS report where these functions are identified with those 
computable by Myhill's deterministic linearly bounded automata. Parikh 
[1971 JSL] proved also that these are the provably total functions of 
his "Bounded Peano Arithmetic" PB, which today is known as I\Delta_0. 
Parikh's reconstrual of effectiveness in terms of what can be carried 
out in bounded arithmetic is of a more logical or philosophical nature 
than a CS nature. It is worth noting that Parikh directly addresses in 
that study the current question "... on Church's Thesis. One may still 
accept recursive = effective but would not accept the classical proof 
that [all prim. rec. functions are recursive]. Rather the provably 
recursive functions of PB ... may have more claim to be the class of 
effective functions" [pg. 506].

Curtis Franks
Dept. Logic and Philosophy of Science
University of California, Irvine