On Completeness and Decidability of Phase Space Invertible Asynchronous Cellular Automata

Issue title: Cellular Automata and Models of Computation

Article type: Research Article

Authors: Wacker, Simon | Worsch, Thomas

Affiliations: Department of Informatics, Karlsruhe Institute of Technology, D-76128 Karlsruhe, Germany. simon.wacker@student.kit.edu; worsch@kit.edu

Note: [] Address for correspondence: Department of Informatics, Karlsruhe Institute of Technology, Public Relations, D-76128 Karlsruhe, Germany

Abstract: While for synchronous deterministic cellular automata there is an accepted definition of reversibility, this is not the case for asynchronous cellular automata. We first discuss a few possibilities and then investigate what we call phase space invertible asynchronous cellular automata. We will show that for each Turing machine there is a phase space invertible purely asynchronous cellular automaton simulating it and that it is decidable whether an arbitrary-dimensional purely and a one-dimensional fully asynchronous cellular automaton is phase space invertible.

DOI: 10.3233/FI-2013-876

Journal: Fundamenta Informaticae, vol. 126, no. 2-3, pp. 157-181, 2013