On the density of honest subrecursive classes

DOI10.1016/S0022-0000(75)80039-0zbMath0336.02031MaRDI QIDQ1229713

Michael Machtey

Publication date: 1975

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items

Reductions among polynomial isomorphism types, The structure of the honest polynomial m-degrees, Indexings of subrecursive classes, Streamlined subrecursive degree theory, Semi-honest subrecursive degrees and the collection rule in arithmetic, A maximal sequence of classes transformable by primitive recursion in a given class, Honest elementary degrees and degrees of relative provability without the cupping property, Augmented loop languages and classes of computable functions, Polynomial and abstract subrecursive classes, Subrekursive Komplexität bei Gruppen. II: Der Einbettungssatz von Higman für entscheidbare Gruppen, Cook reducibility is faster than Karp reducibility in NP, Finite complete rewriting systems and the complexity of word problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Augmented loop languages and classes of computable functions
• On a Subrecursive Hierarchy and Primitive Recursive Degrees
• Gödel numberings of partial recursive functions
• Classes of Predictably Computable Functions
• The honest subrecursive classes are a lattice
• A Machine-Independent Theory of the Complexity of Recursive Functions
• A Classification of the Recursive Functions