[40] Consider an online deterministic Turing machine with a one-way input tape, some work tapes/pushdown stores and a oneway output tape. The result of computation is written on the output tape. ‘Online simulation’ means that after reading a new input symbol the simulating machine must write down precisely the output of the simulated machine for the processed initial input segment before it goes on to read the next input symbol. Prove the following:

(a) It requires Ω(n(log n)1/(k+1)) time to online simulate k+1 pushdown stores by k tapes.

(b) Online simulating one tape plus k−1 pushdown stores by k pushdown stores requires Ω(n(log n)1/(k+1)) time.

(c) Each of the aforementioned lower bounds holds also for a probabilistic simulation where the probabilistic simulator flips a random coin to decide the next move. (No error is allowed. The simulation time is the average taken over all coin-tossing sequences.)

Comments. Item

(a) is from W.J. Paul [Inform. Contr., 53(1982), 1–

8]. Item

(b) is due to P. Dˇuriˇs, Z. Galil, W.J. Paul, and R. Reischuk

[Inform. Contr., 60(1984), 1–11]. Item

(c) is from [R. Paturi, J. Simon,

R. Newman-Wolfe, and J. Seiferas, Inform. Comput., 88(1990), 88–104].
The last paper also includes proofs for Items

(a) and (b).