General iteration and unary functions

DOI10.1016/0168-0072(91)90029-LMaRDI QIDQ1182467zbMATH OpenFDO

Authors G. M. Germano, S. Mazzanti

Publication date 28 June 1992

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0168-0072(91)90029-L

zbMATH Keywords

general computable functionpartial recursive functionswhile-do iteration operator

Mathematics Subject Classification ID

Recursive functions and relations, subrecursive hierarchies (03D20) Theory of computing (68Q99)

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.

Recommendations

• Primitive iteration and unary functions
• scientific article; zbMATH DE number 6287652
• Unary primitive recursive functions
• Succinct iterative characterizations of primitive computable unary functions

Cites work

• A flow diagram composition of Markov's normal algorithms without concluding formulas
• A Note on Primitive Recursive Functions
• A note on recursive functions
• Closure functions and general iterates as reflectors
• Computable stack functions for semantics of stack programs
• General iteration and unary functions
• General Recursive Functions
• General recursive functions of natural numbers
• scientific article; zbMATH DE number 3881860 (Why is no real title available?)
• scientific article; zbMATH DE number 4033724 (Why is no real title available?)
• scientific article; zbMATH DE number 4085875 (Why is no real title available?)
• scientific article; zbMATH DE number 3506659 (Why is no real title available?)
• scientific article; zbMATH DE number 3537652 (Why is no real title available?)
• scientific article; zbMATH DE number 3335016 (Why is no real title available?)
• ITERATION AND RECURSION
• On folk theorems
• Primitive iteration and unary functions
• Primitive recursive functions
• Primitive Recursive Functions. II
• Proving a compiler correct: A simple approach
• Recursion and double recursion
• Recursive Functions of One Variable
• Sequence recursiveness without cylindrification and limited register machines
• Sequence-to-sequence recursiveness
• Simplifications of the recursion scheme
• Undecidable theories

Cited in

(10)

• Iterated images on manifolds
• Primitive iteration and unary functions
• General iteration and unary functions
• Ein Kriterium für die Primitive Rekursivität der Funktional‐Iteration
• scientific article; zbMATH DE number 29625 (Why is no real title available?)
• Iterative Characterizations of Computable Unary Functions: A General Method
• Iteration on notation and unary functions
• Succinct iterative characterizations of primitive computable unary functions
• Closure functions and general iterates as reflectors
• Unary functions

This page was built for publication: General iteration and unary functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1182467)