SIMULATIONS AK)NG MULTIDIMENSIONAL TUBING MACHINES
C. Loui · 1981
For all d ~ 1 and all e > d, every determin istic multihead e-dimensional Turing machine of time complexity T(n) can be simulated on-line by a deterDdnistic multihead_ d-dimensional Turing machine in time O(T(n)l+l/d-l/e(log T(n})O(l». This simu lation almost achieves the known lower bound 1+1/d-1/e n (T (n) ) on the time required. Furthermore, there is a deterministic d-dimensional machine with just two worktape heads that simulates the e-dimen sional machine on-line in time O(T(n)l+l/d-l/delog T(n». These simulations are interpreted in terms of dynamic embeddings among data- structures.