Primitive iteration and unary functions
type: Item
instance of: scholarly article
title: Primitive iteration and unary functions
zbMATH Open document ID: 0664.68047
DOI: 10.1016/0168-0072(88)90032-2
published in: Annals of Pure and Applied Logic
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03D60
Mathematics Subject Classification ID: 03D20
zbMATH DE Number: 4087020
zbMATH Keywords: computable functions. primitive recursive sequence functions
zbMATH Keywords: primitive recursive unary functions
author: G. M. Germano
author: S. Mazzanti
reviewed by: Andrea Maggiolo-Schettini
MaRDI profile type: Publication
full work available at URL: 0168-0072(88)90032-2
OpenAlex ID: W2090640026
cites work: Q5331549
cites work: ITERATION AND RECURSION
cites work: Q5612462
cites work: Comparing Hierarchies of Primitive Recursive Sequence Functions
cites work: Q5572358
cites work: Equivalence of partial recursivity and computability by algorithms without concluding formulas
cites work: Q4087154
cites work: Sequence-to-sequence recursiveness
cites work: Sequence recursiveness without cylindrification and limited register machines
cites work: Q3216120
cites work: Q3773864
cites work: General Recursive Functions
cites work: A Note on Primitive Recursive Functions
cites work: Recursive Functions of One Variable
cites work: A classification of an iterative hierarchy
cites work: A reduction of the recursion scheme
cites work: Simplifications of the recursion scheme
cites work: Q5639839
cites work: A classification of the one-argument primitive recursive functions
cites work: Another simplification of the recursion scheme
cites work: Classes of One‐Argument Recursive Functions
cites work: Primitive recursive functions
cites work: Primitive Recursive Functions. II
cites work: On the Algebraic Structure of Primitive Recursive Functions
cites work: Computability of Recursive Functions
cites work: Q5732648
cites work: Q5616133
description: scientific article; zbMATH DE number 4087020