On Time versus Space II

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.

Authors

• Wolfgang J. Paul
• Rüdiger Reischuk

Keywords

• Turing machines
• Multidimensional systems
• Costs
• Computational modeling
• Computational complexity
• Time measurement
• Writing
• Turing Machine