Computational complexity of random access stored program machines

DOI10.1007/BF01694180zbMath0222.68020OpenAlexW2014637829MaRDI QIDQ5627619

Juris Hartmanis

Publication date: 1971

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

Full work available at URL: https://doi.org/10.1007/bf01694180

Mathematics Subject Classification ID

Mathematical problems of computer architecture (68M07) Information storage and retrieval of data (68P20)

Related Items

From Turing machines to computer viruses ⋮ Predecessor machines ⋮ A survey of state vectors ⋮ Priority queues with update and finding minimum spanning trees ⋮ Nonexistence of program optimizers in several abstract settings ⋮ A characterization of the power of vector machines ⋮ On non-determinacy in simple computing devices ⋮ Berechnung und Programm. II ⋮ Time bounded random access machines ⋮ Parallel random access machines with powerful instruction sets

Cites Work

• Real time computation
• Tape-reversal bounded Turing machine computations
• On the Computational Complexity of Algorithms
• Classes of computable functions defined by bounds on computation
• Two-Tape Simulation of Multitape Turing Machines
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Computational Complexity of One-Tape Turing Machine Computations
• Random-Access Stored-Program Machines, an Approach to Programming Languages
• One-tape, off-line Turing machine computations