[O44] Obtain a tight bound for simulating two work tapes by one work tape for Turing machines with a two-way input tape.

Comments. W. Maass, G. Schnitger, E. Szemer´edi, and G. Turan, [Computational Complexity, 3(1993), 392–401] proved (not using Kolmogorov complexity) the following: Let L = {A#B : A = Bt and aij = 0 only when i, j ≡ 0 mod (log m), where m = 2k, for some k, is the size of matrices}. Accepting L requires Ω(n log n) time on a Turing machine with a two-way input tape and one work tape. Since L can be accepted in O(n) time by a similar machine with two work tapes, this result implies that two tapes are better than one for deterministic Turing machines with a two-way input tape. An upper bound to this question is given in Exercise 6.10.10, Item (c).