Subrecursiveness: Machine-independent notions of computability in restricted time and storage

DOI10.1007/BF01706069zbMath0229.68013MaRDI QIDQ5637881

David B. Thompson

Publication date: 1972

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Mathematics Subject Classification ID

Related Items

V-comprehensions and P space, Some observations on the connection between counting and recursion, A time-space hierarchy between polynomial time and polynomial space, Nondeterministic stack register machines, Computation models and function algebras, A characterization of functions over the integers computable in polynomial time using discrete ordinary differential equations, Complexity of algorithms and computations, Unnamed Item, Complexity of computable functions for a generalized storage measure, Machine-independent description of certain machine complexity classes, Ein Modell des P=NP-Problems mit einer positiven Lösung, Theories with self-application and computational complexity., A recursive and a grammatical characterization of the exponential-time languages, Axiomatizing Resource Bounds for Measure

Cites Work

• Theory of Formal Systems. (AM-47)
• Classes of Predictably Computable Functions
• Two-Tape Simulation of Multitape Turing Machines
• One-tape, off-line Turing machine computations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item