On a complexity-based way of constructivizing the recursive functions

DOI10.1007/BF00401559MaRDI QIDQ922528zbMATH OpenFDO

Authors F. W. Kroon, Walter A. Burkhard

Publication date 1990

Published in Studia Logica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF00401559

zbMATH Keywords

constructively computable functionconstructivization of recursive functionshierarchies

Mathematics Subject Classification ID

Recursive functions and relations, subrecursive hierarchies (03D20)

Review text

This paper discusses the problem of constructivizing the recursive functions. Various attempts to this problem have been analysed. It is suggested that the class of effectively (or constructively) computable functions can be captured with a broad possibility by some type of hierarchies which are based on some kind of complexity defined in the paper. The hierarchies of this type can be constructively generated, and will be (under some conditions) progressive as being shown in the main theorem of the paper.

Recommendations

• scientific article; zbMATH DE number 218515
• Effective choice of constructivizations and recursive consistency of problems on constructive models
• scientific article; zbMATH DE number 2013793
• On effective choice of constructivizations
• scientific article; zbMATH DE number 65741

Cites work

• A Hierarchy of Primitive Recursive Functions
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Augmented loop languages and classes of computable functions
• Classes of Predictably Computable Functions
• Computability of Recursive Functions
• Extension of an effectively generated class of functions by enumeration
• scientific article; zbMATH DE number 3882394 (Why is no real title available?)
• scientific article; zbMATH DE number 3454788 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3083488 (Why is no real title available?)

Cited in

(5)

• Recursive constructions for large caps
• The intrinsic difficulty of recursive functions
• scientific article; zbMATH DE number 3900732 (Why is no real title available?)
• scientific article; zbMATH DE number 2114136 (Why is no real title available?)
• Tailoring recursion for complexity

This page was built for publication: On a complexity-based way of constructivizing the recursive functions

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