[FOM] Recursive but not p.r. computable functions

[Jeff Hirst]

Hi-

One could construct some examples of recursive (but not p.r.) functions
based on Paris-Harrington style functions or the functions related
to Goodstein sequences.  For example, using the definitions from
Mill's and Erdos' paper "Some Bounds for the Ramsey-Paris-Harrington
Numbers", the function R_k(k) is recursive but not p.r.  Although
the function is certainly a diagonalization of a sequence of functions,
it can be defined without emphasizing the diagonal nature.

My favorite article on the Goodstein sequences is E. Adam Chicon's
"A short proof of two recently discovered independence results
using recursion theoretic methods."  The number of steps before
Chicon's "process 1" terminates is rec. but not p.r. and not
so apparently the result of a diagonalization process.

If you need more extended references, I can provide them.

-Jeff
-- 
Jeff Hirst   jlh at math.appstate.edu
Professor of Mathematics
Appalachian State University, Boone, NC  28608
vox:828-262-2861    fax:828-265-8617