Primitive iteration and unary functions (Q1115608)

The paper studies iterative characterizations of primitive computable unary functions. The motivation for considering iterative characterizations comes from programming languages where iterative constructs are widely used and from the convenience that one may have, e.g., in proving by induction that a given language computes all the primitive recursive functions. The paper starts from giving a number of characterizations of \(prim({\mathbb{N}}^ a, {\mathbb{N}}^ b)\), the family of primitive recursive sequence functions, by means of different iteration and composition operators. Then corresponding characterizations are given for prim(\({\mathbb{N}}, {\mathbb{N}})\), the family of primitive recursive unary functions, by constructing conjugates with respect to a general pairing function. Other characterizations are obtained by using a Cantor-like pairing and a Gödel-like pairing.