Augmented loop languages and classes of computable functions

DOI10.1016/S0022-0000(72)80032-1zbMath0312.68028OpenAlexW2144600960MaRDI QIDQ1219687

Michael Machtey

Publication date: 1972

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(72)80032-1

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Recursive functions and relations, subrecursive hierarchies (03D20) General topics in the theory of software (68N01)

Related Items (11)

Streamlined subrecursive degree theory ⋮ Semi-honest subrecursive degrees and the collection rule in arithmetic ⋮ On a complexity-based way of constructivizing the recursive functions ⋮ Honest elementary degrees and degrees of relative provability without the cupping property ⋮ An operator embedding theorem for complexity classes of recursive functions ⋮ Polynomial and abstract subrecursive classes ⋮ On the density of honest subrecursive classes ⋮ On computational reducibility ⋮ On languages specified by relative acceptance ⋮ On the computational complexity of imperative programming languages ⋮ Relativization of the Theory of Computational Complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the density of honest subrecursive classes
• On the structure of subrecursive degrees
• The upper semi-lattice of degrees of recursive unsolvability
• Extension of an effectively generated class of functions by enumeration
• On a Subrecursive Hierarchy and Primitive Recursive Degrees
• Gödel numberings of partial recursive functions
• Classifications of Recursive Functions by Means of Hierarchies
• The honest subrecursive classes are a lattice
• On the Computational Complexity of Algorithms
• Classes of computable functions defined by bounds on computation
• Degrees of Unsolvability. (AM-55)
• A Machine-Independent Theory of the Complexity of Recursive Functions
• A Classification of the Recursive Functions
• Computational speed-up by effective operators
• A Hierarchy of Primitive Recursive Functions

This page was built for publication: Augmented loop languages and classes of computable functions