Fast simulation of Turing machines by random access machines
Authors:Jyrki Katajainen, Jan van Leeuwen, and Martti Penttonen
Published in:SIAM Journal on Computing 17,1 (1988), 77-88
Full text:<pdf.gif>PDF (768 kB)  
Copyright:© Society for Industrial and Applied Mathematics
Abstract:We prove that a T(n) time-bounded, S(n) space-bounded and U(n) output-length-bounded Turing machine can be simulated in O(T(n) + (n + U(n)) log log S(n)) time by a random access machine (with no multiplication or division instructions) under the logarithmic cost criterion.
  author = {Jyrki Katajainen and Jan van Leeuwen and Martti Penttonen},
  title = {Fast simulation of {T}uring machines by random access machines},
  journaltitle = {SIAM Journal on Computing},
  volume = {17},
  number = {1},
  year = {1988},
  pages = {77--88},
This page was generated by Jyrki Katajainen <> on 31.12.2011.