The realm of primitive recursion (Q1112020): Difference between revisions

This paper provides a unifying treatment for the various forms of primitive recursion. It utilizes hints found in \textit{R. Péter}'s classic book: Recursive functions (1967; Zbl 0154.006). Let \({\mathcal J}\) be the set of functions: \(N\to N\). For a given \(g\in {\mathcal J}\) and a functional H: \(N^ 2\times {\mathcal J}\to N\), let \(f(0,x)=g(x)\), \(f(r+1,x)=H(r,x\); \(\lambda\) zf(r,z)). Simmons identifies an effective class \({\mathcal H}\) of functionals such that (i) all known refinements of primitive recursion may be cast in the above form with H drawn from \({\mathcal H}\), and (ii) when f is so defined and \(H\in {\mathcal H}\), f is primitive recursive in g and a systematic reduction to a standard primitive recursive definition can be given. \({\mathcal H}\) is a proper subclass of the class of all primitive recursive functionals of appropriate arity. The latter class is itself seen to be too broad for the purpose at hand, since it enables diagonalization out of the primitive recursive functions.