The difference between one tape and two tapes: With respect to reversal complexity
Jianer Chen · Theoretical Computer Science · 1990
Reversal complexity on 1-tape and 2-tape Turing machine models discussed. We show that with respect to reversal complexity there is an intrinsic difference between 1-tape and 2-tape Turing machines. More precisely, we show that in the deterministic case, 2-tape Turing machines can simulate k-tape Turing machines without much increase in reversals while 1-tape Turing machines do not have such a property if P ≠ PSPACE; in the nondeterministic case, reversal complexity is “too” powerful to be a complexity measure on 2-tape Turing machines, but on 1-tape Turing machines it is a reasonable complexity measure which is linearly related to the space complexity.