[FOM] Parson's Thesis?
cfranks at uci.edu
Wed Aug 10 16:03:42 EDT 2005
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].
Dept. Logic and Philosophy of Science
University of California, Irvine
More information about the FOM