Reversibility in space-bounded computation

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.

Keywords:

• reversible computing
• reversibility
• determinism
• space complexity
• space- bounded Turing machine
• symmetric Turing machine

Notes

This work was supported, in part, by JSPS KAKENHI [grant number 24500017].