The difference between one tape and two tapes: With respect to reversal complexity (Q920983): Difference between revisions
From MaRDI portal
Latest revision as of 11:31, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The difference between one tape and two tapes: With respect to reversal complexity |
scientific article |
Statements
The difference between one tape and two tapes: With respect to reversal complexity (English)
0 references
1990
0 references
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.
0 references
time complexity
0 references
simulation of k-tape Turing machines
0 references
number of alternations
0 references
reversal complexity
0 references
space complexity
0 references