Abstract
In this paper, we investigate how computing power of a space-bounded Turing machine (TM) is affected by reversibility and determinism. We show an irreversible deterministic TM (IDTM), and a reversible non-deterministic TM (RNTM) can be simulated by a reversible and deterministic TM (RDTM) that uses exactly the same numbers of storage tape symbols and storage tape squares. Thus, an RDTM has relatively high capability in spite of the constraints of reversibility and determinism. Here, we also discuss a space-bounded symmetric TM.
Notes
This work was supported, in part, by JSPS KAKENHI [grant number 24500017].