The complexity of on-line simulations between multidimensional turing machines and random access machines

To study different implementations of arrays, we present four results on the time complexities of on-line simulations between multidimensional Turing machines and random access machines (RAMs). First, everyd-dimensional Turing machine of time complexityt can be simulated by a log-cost RAM running inO(t(logt)^1–(1/d)(log logt)^1/d) time. Second, everyd-dimensional Turing machine of time complexityt can be simulated by a unit-cost RAM running inO(t/(logt)^1/d) time, provided that the input length iso(t/(logt)^1/d). Third, there is a log-cost RAMR of time complexityO(n), wheren is the input length, such that, for anyd-dimensional Turing machineM that simulatesR on-line,M requires (n ^{1 + (1/d)})/(logn(log logn)^{1 + (1/d)})) time. Fourth, every unit-cost RAM of time complexityt can be simulated by ad-dimensional Turing machine inO(t ²(logt)^1/2) time ifd = 2, and inO(t ²) time ifd 3. This result uses the weight-balanced trees of Nievergelt and Reingold.This paper was prepared while M. C. Loui was visiting the National Science Foundation in Washington, DC, and the Institute for Advanced Computer Studies, University of Maryland, College Park, MD. The views, opinions, and conclusions in this paper are those of the authors and should not be construed as an official position of the National Science Foundation, Department of Defense, U.S. Air Force, or any other U.S. government agency. The research of M. C. Loui was supported by the National Science Foundation under Grant CCR-8922008.