Publication:4934292

zbMath0942.68049MaRDI QIDQ4934292

Peter Clote

Publication date: 13 July 2000

zbMATH Keywords

survey; function algebra; complexity classes; computation model; primitive recursive functions; recursion scheme; computable function; quantifier hierarchies; type 2 functional

Mathematics Subject Classification ID

03-02: Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

03D20: Recursive functions and relations, subrecursive hierarchies

03D10: Turing machines and related notions

Related Items

A proof-theoretic characterization of the basic feasible functionals, Complexity-theoretic hierarchies induced by fragments of Gödel's \(T\), A foundation for real recursive function theory, Implicit characterizations of FPTIME and NC revisited, Theories with self-application and computational complexity., Continuous-time computation with restricted integration capabilities, Safe recursion with higher types and BCK-algebra, A survey of recursive analysis and Moore's notion of real computation, Separating NC along the \(\delta\) axis, On the computational complexity of imperative programming languages, An analog characterization of the Grzegorczyk hierarchy, A characterization of alternating log time by ramified recurrence, A feasible theory of truth over combinatory algebra, A Characterisation of the Relations Definable in Presburger Arithmetic, Pure Iteration and Periodicity