The realm of primitive recursion
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.
- Implicit characterizations of FPTIME and NC revisited
- Rudimentary relations and primitive recursion: A toolbox
- A note on complexity measures for inductive classes in constructive type theory
- Ramified recurrence and computational complexity. III: Higher type recurrence and elementary complexity
- Functions over free algebras definable in the simply typed lambda calculus
- Unification of infinite sets of terms schematized by primal grammars
- Analysing the implicit complexity of programs.
- Higher type recursion, ramification and polynomial time
- Separating NC along the \(\delta\) axis
- On the computational complexity of imperative programming languages
- A characterization of alternating log time by ramified recurrence
- Implicit recursion-theoretic characterizations of counting classes
- A new order-theoretic characterisation of the polytime computable functions
- An arithmetic for polynomial-time computation
- Two function algebras defining functions in \(\mathsf{NC}^k\) Boolean circuits
- Build your own clarithmetic. I: Setup and completeness
- Pointwise transfinite induction and a miniaturized predicativity
- Tiering as a Recursion Technique
- Recursion Schemata for NC k
- Dependency Pairs and Polynomial Path Orders
- scientific article; zbMATH DE number 23837 (Why is no real title available?)
- A new “feasible” arithmetic
- The Recursive Core
- Tiered arithmetics
- Primitive recursive real numbers
- Intrinsic theories and computational complexity
- Characterizing parallel time by type 2 recursions with polynomial output length
- Term rewriting theory for the primitive recursive functions
- Recursion-theoretic alternation
This page was built for publication: The realm of primitive recursion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1112020)
