[FOM] Parson's Thesis? [A primitive recursive analogue of the Church-Turing thesis]

Rex Butler rexbutler at hotmail.com
Wed Aug 3 00:25:09 EDT 2005

First, an excerpt from the abstract of "A simple proof of Parsons’ theorem" 
by Fernando Ferreira, published in the Notre Dame Journal of Formal Logic. 
See http://alf1.cii.fc.ul.pt/~ferferr/yet.pdf for example.

"Let I-Sigma_1 be the fragment of elementary Peano Arithmetic in
which induction is restricted to Sigma_1-formulas. More than three decades
ago, Charles Parsons showed that the provably total functions of I-Sigma_1 
exactly the primitive recursive functions. "

Putting this aside for a moment, let E be a class of "elementary iterations" 
in a stepwise computation model.  Modulo coding, we may assume the functions 
in E are number theoretic.  Possible choices include weak classes like 
Turing transition functions, medium classes like the Delta_0 functions (in 
PA) and primitive recursive functions, and strong classes such as the 
multiply recursive functions.

Now I had long wondered if there was a canonical choice for E, and after 
seeing Parson's theorem it seems the primitive recursive functions are a 
good choice, given the constructive nature of Sigma_1.


1.  What can be said about the canonical nature of the primitive recursive 

2.  Can they reasonably be associated with the intuitive class of 
"elementary iterations" in turing-equivalent computation models?

3.  Would this make a reasonable thesis?   Has it been stated as such?

3.  [Broadly] I find Parsons' theorem intriguing because it recovers a 
subrecursive class from the recursive functions.  Are there other seemingly 
canonical classes of provably recursive functions?

    Rex Butler

[Note to moderator:  I hope this revision suffices.]

More information about the FOM mailing list