Reversal-Bounded Computations
No Access Until
Permanent Link(s)
Collections
Other Titles
Author(s)
Abstract
IN computations by abstract computing devices such as the Turing machine, head reversals are required for searching the input or retrieving intermediate results. Hence the number of head reversals is a measure of the complexity of a computation. This thesis is a study of reversal-bounded computation on three models of abstract computing devices. The first model is the 1-tape Turing machine with finite bounds on head reversals. It is known that such machines recognize exactly the regular sets so that for recognition purposes, reversals can be eliminated entirely. For transduction purposes, that is, if an output is expected on the tape, a single reversal suffices. Hence these machines are most appropriately called finite automata. Clearly they are among the weakest possible computing devices, and many decision problems about them are solvable. We use this fact and a very simple input-output encoding scheme to obtain greatly simplified proofs of the decidability of some weak mathematical theories, including the weak monadic second-order theory of one successor and Presburger arithmetic. Similar techniques yield linear size bounds as well as linear time complexity bounds (on the multitape Turing machine model) for functions definable in Presburger arithmetic. As corollaries, we find applications in linear diophantine systems and linear integer programming. The second model is the multicounter machine with general bounds on counter reversals. By relating counter reversal to time and space, we show that recursiveness of reversal bounds implies recursiveness of the sets accepted. For bounds that are at least linear, counter reversal is polynomially equivalent to Turing machine time in both the deterministic and the nondeterministic cases. This result leads to a general deterministic reversal hierarchy and a natural formulation fo the P=?NP question on the multicounter machine model. It also suggests that on every reasonable universal computing model, there is a "natural" complexity measure that is polynomially equivalent to Turing machine time. For reversal bounds that grow more slowly than