[38] Consider the machine models in Exercise 6.10.13, Item

(c). All machines have one multidimensional tape with one head.

(a) Show that an l-dimensional machine running in time T can be simulated by a probabilistic k-dimensional machine running in time O(T r(log T )1/k), where r =1+1/k − 1/l.

(b) Show that a probabilistic k-dimensional machine requires time Ω(T r)

to simulate an l-dimensional machine running in time T , where r =

1+1/k − 1/l.

Comments. Source: [N. Pippenger, Proc. 14th ACM Symp. Theory Comput., 1982, pp. 17–26]. Pippenger used Shannon’s information measure to prove Item (b).