Fast Simulation of Turing Machines by Random Access Machines

DOI10.1137/0217005zbMath0657.68048OpenAlexW2081339104MaRDI QIDQ3805901

Jan van Leeuwen, Martti Penttonen, Jyrki Katajainen

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

Turing machinesrandom access machinessimulation overheads

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (4)

Invariance properties of RAMs and linear time ⋮ The problem of space invariance for sequential machines ⋮ The complexity of on-line simulations between multidimensional turing machines and random access machines ⋮ Sorting, linear time and the satisfiability problem

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