The difference between one tape and two tapes: With respect to reversal complexity (Q920983)

Reversal complexity refers to the number of alternations in the moving of a head on the tape of a Turing machine. The paper deals with the study of the reversal complexity on 1-tape and 2-tape Turing machines. For the deterministic case, it is proven that a Turing machine with a single work tape cannot simulate a k-tape Turing machine in an efficient way provided that \(P\neq PSPACE\). A result, shown in a previous paper, claims that a k- tape Turing machine can be simulated by a 2-tape Turing machine without much loss of reversal resource. The two results indicate the 2-tape Turing machine model appropriate for the study of reversal complexity. For the nondeterministic case, the correlation between space complexity and reversal complexity on the 1-tape Turing machine model is studied. B. S. Backer and R. V. Book (1968) showed that the 2-tape Turing machine model is too strong for reversal complexity. In contrast to this result, the present paper shows that reversal complexity is linearly related to space complexity for the case of 1-tape Turing machines. A list of valuable remarks ends the paper.