The Time Measure of One-Tape Turing Machines Does Not Have the Parallel Computation Property
Joachim Biskup · SIAM Journal on Computing · 1978
J. Hartmanis conjectured that the time measure of one-tape Turing machines does not have the parallel computation property. We prove this conjecture by constructing one-tape Turing machines $M_1 $ and $M_2 $ such that no one-tape Turing machine can simulate them in parallel. This is shown using a result of F. C. Hennie that nonregular sets cannot be accepted in linear time.