UNARY PRIMITIVE RECURSIVE FUNCTIONS

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 composition and iteration of certain optimal sets. §1. Introduction. Prim, i.e. the set of primitive recursive functions, is the closure under composition and primitive recursion of zero, successor and projection functions. For a detailed definition, the reader is referred to any standard work, for instance chapter 1 of [8]. A suitable subset is Prim(N, N), i.e. the set of unary primitive recursive functions, that will be one of the objects of our