Title :
On time versus space II
Author :
Paul, W.J. ; Reischuk, R.
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 :
Computational complexity; Computational modeling; Costs; Multidimensional systems; Time measurement; Turing machines; Writing;
Conference_Titel :
Foundations of Computer Science, 1979., 20th Annual Symposium on
Conference_Location :
San Juan, Puerto Rico
DOI :
10.1109/SFCS.1979.30
