On the Power of Reversals Over the Input Tape of Off-Line Turing Machines

Hiroaki YAMAMOTO

Summary :

For reversal complexity on an off-line Turing machine, which is a Turing machine with a read-only two-way input tape except work-tapes, we can consider two kinds of definition; the first one is a definition in which the number of reversals over the input tape is not counted, and the second one is a definition in which it is counted. Unlike time and space complexities, whether or not there is any difference between these two definitions does not seem to be trivial. In this paper, we will show the following results: (1) let S(n) be any function, and R(n) be an (R(n), S(n)) reversal-space constructible function. Then, DRESP_k(R(n), S(n)) IDRESP_k+2(R(n) + log(nS(n)), n²R(n)S(n)), (2) let R(n) and S(n) be any functions. Then, NRESP_k(R(n), S(n)) INRESP_k+1(R(n), n²S(n)), and ARESP_k(R(n), S(n)) = IARESP_k(R(n), S(n)), where DRESP denotes a deterministic reversal- and space-bounded class under the definition disregarding reversals over the input tape, and IDRESP denotes a deterministic reversal- and space-bounded class under the definition counting it. The suffix k denotes the number of work-tapes. The classes NRESP, INRESP, ARESP and IARESP are also defined similarly for NTMs and ATMs.

• Publication: IEICE TRANSACTIONS on Information Vol.E79-D No.11 pp.1495-1502
• Publication Date: 1996/11/25
• Type of Manuscript: PAPER
• Category: Algorithm and Computational Complexity

Authors

Hiroaki YAMAMOTO

Keyword

reversal complexity,  off-line Turing machine,  NC