Classes of computable functions defined by bounds on computation

DOI10.1145/800169.805423MaRDI QIDQ5402507zbMATH OpenOpenAlexFDO

Authors Edward M. McCreight, Albert R. Meyer

Publication date 14 March 2014

Published in Proceedings of the first annual ACM symposium on Theory of computing - STOC '69 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/800169.805423

Mathematics Subject Classification ID

Recursive functions and relations, subrecursive hierarchies (03D20) Recursively (computably) enumerable sets and degrees (03D25)

Recommendations

• On classes of computable functions
• scientific article; zbMATH DE number 4112573
• A new characterization of computable functions
• scientific article; zbMATH DE number 1136092
• Computability theory of generalized functions
• A taxonomy of complexity classes of functions
• scientific article; zbMATH DE number 4033742
• scientific article; zbMATH DE number 1746042
• scientific article; zbMATH DE number 2089959
• On the Computable Theory of Bounded Analytic Functions

Cited in

(36)

• Complexity of algorithms and computations
• Two types of properties for complexity measures
• Almost everywhere high nonuniform complexity
• Program schemata with polynomial bounded counters
• Augmented loop languages and classes of computable functions
• The non-renamability of honesty classes
• Complexity classes of partial recursive functions
• An operator embedding theorem for complexity classes of recursive functions
• Polynomial and abstract subrecursive classes
• On computational reducibility
• Complexity-class-encoding sets
• Some applications of the McCreight-Meyer algorithm in abstract complexity theory
• A note on complexity measures for inductive classes in constructive type theory
• On the interplay between inductive inference of recursive functions, complexity theory and recursive numberings
• Predicatively computable functions on sets
• Relationships between nondeterministic and deterministic tape complexities
• The enumerability and invariance of complexity classes
• Subrecursive programming languages. II. On program size
• Abstract computational complexity and cycling computations
• Effective operators with no strong gaps
• Degrees of computational complexity
• Reverse complexity
• scientific article; zbMATH DE number 3958737 (Why is no real title available?)
• Easy Constructions in Complexity Theory: Gap and Speed-Up Theorems
• Relativization of the Theory of Computational Complexity
• The operator gap theorem in α-recursion theory
• scientific article; zbMATH DE number 2061073 (Why is no real title available?)
• scientific article; zbMATH DE number 1827830 (Why is no real title available?)
• On classes of computable functions
• From Logic to Theoretical Computer Science – An Update
• A note on dense and nondense families of complexity classes
• Speed-Ups by changing the order in which sets are enumerated
• Computational complexity of random access stored program machines
• Comparison of identification criteria for machine inductive inference
• Effective category and measure in abstract complexity theory
• Learning recursive functions: A survey

This page was built for publication: Classes of computable functions defined by bounds on computation

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