Classes of computable functions defined by bounds on computation

DOI10.1145/800169.805423zbMath1283.03074OpenAlexW2015666295MaRDI QIDQ5402507

Albert R. Meyer, Edward M. McCreight

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)

Related Items

Reverse complexity, 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, Complexity of algorithms and computations, Two types of properties for complexity measures, Learning recursive functions: A survey, Effective category and measure in abstract complexity theory, 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, Comparison of identification criteria for machine inductive inference, From Logic to Theoretical Computer Science – An Update, Some applications of the McCreight-Meyer algorithm in abstract complexity theory, Relationships between nondeterministic and deterministic tape complexities, A note on complexity measures for inductive classes in constructive type theory, The enumerability and invariance of complexity classes, Subrecursive programming languages. II. On program size, The operator gap theorem in α-recursion theory, Abstract computational complexity and cycling computations, Effective operators with no strong gaps, Degrees of computational complexity, Easy Constructions in Complexity Theory: Gap and Speed-Up Theorems, On the interplay between inductive inference of recursive functions, complexity theory and recursive numberings, Relativization of the Theory of Computational Complexity