Title: Simulations among multidimensional turing machines
Abstract: For all d ⩾ 1 and all e >d, every deterministic multihead e-dimensional Turing machine of time complexity T(n) can be simulated on-line by a deterministic multihead d-dimensional Turing machine in time O(T(n)1+1⧸d−1⧸(log T(n))0(1)). This simulation almost achieves the known lower bound Ω(T(n)1+1⧸d−1⧸e) on the time required. The simulation is interpreted in terms of dynamic embeddings among arrays with local access.