[38] A tree work tape is a complete, infinite, rooted binary tree used as storage medium (instead of a linear tape). A work tape head starts at the root and can in each step move to the direct ancestor of the currently scanned node (if it is not the root) or to either one of the direct descendants. A multihead tree machine is a Turing machine with a one-way linear input tape, one-way linear output tape, and several tree work tapes each with k ≥ 1 heads. We assume that the finite control knows whether two work tape heads are on the same node or not. A d-dimensional work tape consists of nodes corresponding to d-tuples of integers, and a work tape head can in each step move from its current node to a node with each coordinate ±1 of the current coordinates. Each work tape head starts at the origin, which is the d-tuple with all zeros.

A multihead d-dimensional machine is like the multihead tree machine but with d-dimensional work tapes.

(a) Show that simulating a multihead tree machine online by a multihead d-dimensional machine requires time Ω(n1+1/d/ log n) in the worst case.

Hint: Prove this for a tree machine with one tree tape with a single head that runs in real time.

(b) Prove the same lower bound as in Item (a), where the multihead ddimensional machine is made more powerful by allowing the work tape heads also to move from their current node to the current node of any other work tape head in a single step.
Comments. Source: [M.C. Loui, SIAM J. Comput., 12(1983), 463–472].
The lower bound in Item

(a) is optimal, since it can be shown that every multihead tree machine of time complexity t(n) can be simulated online by a multihead d-dimensional machine in time O(t(n)1+1/d/ log t(n)). It is known that every log-cost RAM (Exercise 6.10.17) can be simulated online in real time by a tree machine with one multihead tree tape [W.J. Paul and R. Reischuk, J. Comput. System Sci., 22(1981), 312–
327]. Hence, we can simulate RAMs online by d-dimensional machines in time that is bounded above and below by the same bounds as the simulation of tree machines. See also [M.C. Loui, J. Comput. System Sci., 28(1984), 359–378].