Fast Simulation of Turing Machines by Random Access Machines

DOI10.1137/0217005MaRDI QIDQ3805901zbMATH OpenOpenAlexFDO

Authors Jyrki Katajainen, J. Van Leeuwen, Martti Penttonen

Publication date 1988

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://dspace.library.uu.nl/handle/1874/16296

zbMATH Keywords

random access machinessimulation overheadsTuring machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Fast probabilistic RAM simulation of single tape turing machine computations
• The complexity of on-line simulations between multidimensional turing machines and random access machines
• Deterministic simulation of a single tape turing machine by a random access machine in sub-linear time
• scientific article; zbMATH DE number 177809
• scientific article; zbMATH DE number 3850476

Cited in

(25)

• The problem of space invariance for sequential machines
• Deterministic simulation of a single tape turing machine by a random access machine in sub-linear time
• Feasible real random access machines
• Invariance properties of RAMs and linear time
• Sorting, linear time and the satisfiability problem
• Does indirect addressing matter?
• Simulating Turing machines on Maurer machines
• scientific article; zbMATH DE number 3850476 (Why is no real title available?)
• On efficient simulations of multicounter machines
• Fast probabilistic RAM simulation of single tape turing machine computations
• scientific article; zbMATH DE number 3986645 (Why is no real title available?)
• scientific article; zbMATH DE number 4049049 (Why is no real title available?)
• A nonlinear lower bound for random-access machines under logarithmic cost
• The complexity of on-line simulations between multidimensional turing machines and random access machines
• Optimal On-Line Simulations of Tree Machines by Random Access Machines
• scientific article; zbMATH DE number 1339957 (Why is no real title available?)
• scientific article; zbMATH DE number 4117868 (Why is no real title available?)
• On the notion of bit complexity
• Computing with and without arbitrary large numbers
• scientific article; zbMATH DE number 1396672 (Why is no real title available?)
• On Formalisms for Turing Machines
• Output concepts for accelerated Turing machines
• A seven-head dragon for optimal pattern searching
• Parallel machine models: how they are and where are they going
• Linear speed-up does not hold on Turing machines with tree storages

This page was built for publication: Fast Simulation of Turing Machines by Random Access Machines

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