Reversibility in space-bounded computation
Kenichi Morita · International Journal of General Systems · 2014
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.