Unary primitive recursive functions

DOI10.2178/JSL/1230396909zbMath1158.03023arXivcs/0603063OpenAlexW3102439663MaRDI QIDQ5502807

Daniel Severín

Publication date: 9 January 2009

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Abstract: In this article, we study some new characterizations of primitive recursive functions based on restricted forms of primitive recursion, improving the pioneering work of R. M. Robinson and M. D. Gladstone in this area. We reduce certain recursion schemes (mixed/pure iteration without parameters) and we characterize one-argument primitive recursive functions as the closure under substitution and iteration of certain optimal sets.

Full work available at URL: https://arxiv.org/abs/cs/0603063

zbMATH Keywords

reductionrecursion schemeprimitive recursive function

Mathematics Subject Classification ID

Recursive functions and relations, subrecursive hierarchies (03D20)

Cites Work

• Recursive number theory. A development of recursive arithmetic in a logic-free equation calculus
• Primitive iteration and unary functions
• Classes of recursive functions based on Ackermann's function
• Iteration of relative primitive recursion
• Bounded iteration and unary functions
• A classification of the one-argument primitive recursive functions
• On the Algebraic Structure of Primitive Recursive Functions
• Classes of One‐Argument Recursive Functions
• A reduction of the recursion scheme
• Primitive recursive functions

Related Items (3)

Definitional schemes for primitive recursive and computable functions ⋮ Turing completeness of water computing ⋮ Iteration on notation and unary functions

This page was built for publication: Unary primitive recursive functions