Fast probabilistic RAM simulation of single tape turing machine computations

DOI10.1016/S0019-9958(84)80042-XMaRDI QIDQ3719833zbMATH OpenFDO

Authors John Michael Robson

Publication date 1984

Published in Information and Control (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0019-9958(84)80042-X

zbMATH Keywords

probabilistic random access machine

Mathematics Subject Classification ID

Recommendations

• Fast Simulation of Turing Machines by Random Access Machines
• Deterministic simulation of a single tape turing machine by a random access machine in sub-linear time
• Fast Simulations of Time-Bounded One-Tape Turing Machines by Space-Bounded Ones
• There is no polynomial deterministic space simulation of probabilistic space with a two-way random-tape generator
• A speed-up theorem without tape compression

Cited in

(8)

• Deterministic simulation of a single tape turing machine by a random access machine in sub-linear time
• P-RAM vs. RP-RAM
• scientific article; zbMATH DE number 3848616 (Why is no real title available?)
• scientific article; zbMATH DE number 3934409 (Why is no real title available?)
• There is no polynomial deterministic space simulation of probabilistic space with a two-way random-tape generator
• Fast Simulation of Turing Machines by Random Access Machines
• Optimal On-Line Simulations of Tree Machines by Random Access Machines
• Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories

This page was built for publication: Fast probabilistic RAM simulation of single tape turing machine computations

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