Definitional schemes for primitive recursive and computable functions

Article type: Research Article

Authors: Nielsen, Pace P.^{; *}

Affiliations: Department of Mathematics, Brigham Young University, UT, USA. pace@math.byu.edu

Correspondence: [*] Corresponding author. pace@math.byu.edu.

Abstract: The unary primitive recursive functions can be defined in terms of a finite set of initial functions together with a finite set of unary and binary operations that are primitive recursive in their inputs. We reduce arity considerations, by show that two fixed unary operations suffice, and a single initial function can be chosen arbitrarily. The method works for many other classes of functions, including the unary partial computable functions. For this class of partial functions we also show that a single unary operation (together with any finite set of initial functions) will never suffice.

Keywords: Partial computable function, unary primitive recursive function

DOI: 10.3233/COM-210312

Journal: Computability, vol. 11, no. 1, pp. 1-8, 2022