[48] As in Exercise 6.10.14, consider the Turing machine model of Exercise 6.10.13 but this time with one-dimensional tapes. Show that a Turing machine with two single-head one-dimensional tapes cannot recognize the set {x2x : x ∈ {0, 1}∗ and x is a prefix of x} in real time, although it can do so with three tapes, two two-dimensional tapes, or one two-head tape, or in linear time with just one tape.

Comments. This is considerably more difficult than the problem in Exercise 6.10.14.

In particular, this settles the longstanding conjecture that a two-head Turing machine can recognize more languages in real time if its heads are on the same one-dimensional tape than if they are on separate one-dimensional tapes. Source: partial results in [W.J. Paul, Ibid.; P.M.B. Vit´anyi, J. Comput. System Sci., 29(1984), 303–311]. This 40-year open question was finally settled by T. Jiang, J.I. Seiferas, and P.M.B. Vit´anyi in [J. Assoc. Comp. Mach., 44:2(1997), 237–256].