Phase Space Invertible Asynchronous Cellular Automata
arXiv:1208.2765 · doi:10.4204/EPTCS.90.19
Abstract
While for synchronous deterministic cellular automata there is an accepted definition of reversibility, the situation is less clear for asynchronous cellular automata. We first discuss a few possibilities and then investigate what we call phase space invertible asynchronous cellular automata in more detail. We will show that for each Turing machine there is such a cellular automaton simulating it, and that it is decidable whether an asynchronous cellular automaton has this property or not, even in higher dimensions.
In Proceedings AUTOMATA&JAC 2012, arXiv:1208.2498