On time versus space II

摘要

Every t(n)-time bounded RAM (assuming the logarithmic cost measure) can be simulated by a t(n)/log t(n)-space bounded Turing machine and every t(n)-time bounded Turing machine with d-dimensional tapes by a t(n)5d·log∗t(n)/log t(n)-space bounded machine, where n is the length of the input. A class E of storage structures which generalizes multidimensional tapes is defined. Every t(n)-time bounded Turing machine whose storage structures are in E can be simulated by a t(n) loglog t(n)/log t(n)-space bounded Turing machine.