[FOM] Parson's Thesis? [A primitive recursive analogue of the Church-Turing thesis]
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?
[Note to moderator: I hope this revision suffices.]
More information about the FOM