Reversible Multi-head Finite Automata Characterize Reversible Logarithmic Space

摘要

Deterministic and non-deterministic multi-head finite automata are known to characterize the deterministic and non-deterministic logarithmic space complexity classes, respectively. Recently, Morita introduced reversible multi-head finite automata (RMFAs), and posed the question of whether RMFAs characterize reversible logarithmic space as well. Here, we resolve the question affirmatively, by exhibiting a clean RMFA simulation of logarithmic space reversible Turing machines. Indirectly, this also proves that reversible and deterministic multi-head finite automata recognize the same languages.