The difference between one tape and two tapes: With respect to reversal complexity
type: Item
instance of: scholarly article
title: The difference between one tape and two tapes: With respect to reversal complexity
zbMATH Open document ID: 0709.03033
DOI: 10.1016/0304-3975(90)90178-K
published in: Theoretical Computer Science
publication date: 1990-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03D10
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 4164824
zbMATH Keywords: time complexity
zbMATH Keywords: simulation of k-tape Turing machines
zbMATH Keywords: number of alternations
zbMATH Keywords: reversal complexity
zbMATH Keywords: space complexity
author: Jianer Chen
reviewed by: Dorel Lucanu
MaRDI profile type: Publication
cites work: Reversal-bounded multipushdown machines
cites work: The reduction of tape reversals for off-line one-tape Turing machines
cites work: Tape-reversal bounded Turing machine computations
cites work: One-tape, off-line Turing machine computations
cites work: Q3957949
cites work: Nondeterministic Space is Closed under Complementation
cites work: Relationships between nondeterministic and deterministic tape complexities
full work available at URL: 0304-3975(90)90178-k
OpenAlex ID: W2020818044
description: scientific article; zbMATH DE number 4164824