A machine description and the hierarchy of initial Grzegorczyk classes

DOI10.1007/BF01629435zbMath0493.03012MaRDI QIDQ1168308

Anatoly Petrivich Beltiukov

Publication date: 1982

Published in: Journal of Soviet Mathematics (Search for Journal in Brave)

zbMATH Keywords

complexity classesGrzegorczyk hierarchycontrol deviceSmullyan's rudimentary predicate classstack register machines

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Turing machines and related notions (03D10)

Related Items (7)

Regressive computations characterize logarithmic space ⋮ Deterministic summation modulo \(\mathcal B_{n}\), the semigroup of binary relations on \(0,1, \dots, n-1\) ⋮ Computation models and function algebras ⋮ Arithmetization of register machines with counters ⋮ Computations on register machines with counters ⋮ Register machines with counters ⋮ Nonerasing, counting, and majority over the linear time hierarchy

Cites Work

• Theory of Formal Systems. (AM-47)
• Classes of Predictably Computable Functions
• ÜBER DIE ELIMINIERBARKEIT VON DEFINITIONSSCHEMATA IN DER THEORIE DER REKURSIVEN FUNKTIONEN
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A machine description and the hierarchy of initial Grzegorczyk classes