General iteration and unary functions
type: Item
instance of: scholarly article
title: General iteration and unary functions
zbMATH Open document ID: 0747.03018
DOI: 10.1016/0168-0072(91)90029-L
published in: Annals of Pure and Applied Logic
publication date: 1992-06-28T00:00:00Z
review text: The paper provides a programming-oriented characterization of the class of partial recursive functions. Basically, it is shown that all p.r. functions can be obtained starting with the successor and excess-over-a- square functions by using addition, composition and a while-do iteration operator. Variants of this result, obtained by changing the arity types of functions or by substituting some of the basic operators are also proved. As a by-product, Kleene's normal form theorem is derived in a more precise and programming-oriented setting.
Mathematics Subject Classification ID: 03D20
Mathematics Subject Classification ID: 68Q99
zbMATH DE Number: 31338
zbMATH Keywords: general computable function
zbMATH Keywords: partial recursive functions
zbMATH Keywords: while-do iteration operator
author: G. M. Germano
author: S. Mazzanti
reviewed by: Marius Zimand
MaRDI profile type: MaRDI publication profile
cites work: ITERATION AND RECURSION
cites work: Q5612462
cites work: A flow diagram composition of Markov's normal algorithms without concluding formulas
cites work: Q4087154
cites work: Proving a compiler correct: A simple approach
cites work: Sequence-to-sequence recursiveness
cites work: Q4113810
cites work: Computable stack functions for semantics of stack programs
cites work: Sequence recursiveness without cylindrification and limited register machines
cites work: Q3216120
cites work: Q3773864
cites work: Q3815464
cites work: Primitive iteration and unary functions
cites work: Closure functions and general iterates as reflectors
cites work: Simplifications of the recursion scheme
cites work: On folk theorems
cites work: General recursive functions of natural numbers
cites work: A note on recursive functions
cites work: General Recursive Functions
cites work: A Note on Primitive Recursive Functions
cites work: Recursive Functions of One Variable
cites work: Primitive recursive functions
cites work: Recursion and double recursion
cites work: Primitive Recursive Functions. II
cites work: Undecidable theories
Recommended article: Primitive iteration and unary functions
Recommended article: Q5411500
Recommended article: Unary primitive recursive functions
Recommended article: Succinct iterative characterizations of primitive computable unary functions
description: scientific article; zbMATH DE number 31338