| 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 (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. |
| BibLATEX: | @article{KLP1988J,
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},
}
|