Computational complexity of random access stored program machines

DOI10.1007/BF01694180MaRDI QIDQ5627619zbMATH OpenOpenAlexFDO

Authors J. 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

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

Cites work

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

Cited in

(10)

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

This page was built for publication: Computational complexity of random access stored program machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5627619)