The number of head reversals made during a Turing machine computation has been recognized as an important complexity measure because of its intimate connection to parallel time and circuit depth [1,2]. In this paper, the authors establish a number of important results on reversal complexity, including the following (note that f 2 n is used to mean [ f ( n ) ]2).
A function f ( n ) is reversal-constructible if a two-tape Turing machine exists that, when given the unary representation of an integer n > 0, produces the unary representation of f ( n ) on one of its work tapes, using O ( f ( n ) ) reversals. The authors show that for any reversal-constructible function s ( n ) = &OHgr; ( log n ), DSPACE ( s ( n ) ) ⊆ DREVERSAL ( s ( n ) ). As the authors observe, this result in conjunction with Savitch’s theorem [3] implies that for any reversal-constructible function s ( n ) = &OHgr; ( log n ), NSPACE ( s ( n ) ) ⊆ DREVERSAL ( s 2 ( n ) ). They also show that if the reversal-constructibility requirement on s ( n ) is removed, then DSPACE ( s ( n ) ) ⊆ DREVERSAL ( s 2 ( n ) ) and that NSPACE ( s ( n ) ) ⊆ DREVERSAL ( s 3 ( n ) ).
The authors prove the following tape reduction theorem for reversal complexity. Let r ( n ) = &OHgr; ( log n ). If L is a language accepted by a multi-tape Turing machine with at most r ( n ) reversals, then L is accepted by a two-tape Turing machine with at most O ( r 2 ( n ) ) reversals.
The authors use the above tape reduction to prove a hierarchy theorem for reversal complexity. Specifically, they show that if f ( n ) and g ( n ) are functions such that g 2 ( n ) = o ( f ( n ) ), g ( n ) = &OHgr; ( log n ), and f ( n ) is reversal-constructible, then a language L exists such that L ∈ DREVERSAL ( f ( n ) ) but L ∉ DREVERSAL ( g ( n ) ).
In establishing the above and other results, the authors develop a number of techniques that should prove useful in further work on reversal complexity. The paper is well written and includes a good summary of previous work in this area. I strongly recommend this paper and its companion[4] to anyone interested in complexity theory.
