On time versus space II

1 October 1979

proceedings article
Published by Institute of Electrical and Electronics Engineers (IEEE)

https://doi.org/10.1109/sfcs.1979.30

Abstract

Logarithmically t(n)-time bounded RAMs can be simulated by t(n)/log t(n)-tape bounded Turing machines, t(n)-time bounded multidimensional multitape Turing machines can be simulated by t(n) loglog t(n)/log t(n)-tape bounded Turing machines.

Keywords

TURING MACHINES
MULTIDIMENSIONAL SYSTEMS
COSTS
COMPUTATIONAL MODELING
COMPUTATIONAL COMPLEXITY
TIME MEASUREMENT
WRITING

This publication has 4 references indexed in Scilit:

On Time Versus Space
Journal of the ACM, 1977
Two fast simulations which imply some fast string matching and palindrome-recognition algorithms
Information Processing Letters, 1976
Some Results on Tape-Bounded Turing Machines
Journal of the ACM, 1969
On the Computational Complexity of Algorithms
Transactions of the American Mathematical Society, 1965