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 (31)

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

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