Computation Universality of One-Dimensional Reversible (Injective) Cellular Automata
Kenichi Morita, Masateru Harao · Institutional Repositories DataBase (IRDB) · 1989
A reversible cellular automaton (CA) is a "backward deterministic" CA, i. e_, every configuration of it has at most one predecessor.Toffoli showed that a two-dimensional reversible cellular automaton is computation universal.He posed an open problem whether a one-dimensional reversible CA is computation universal.In this paper, we solve this problem affirmatively.This result is proved by using the previous result of Morita et al. that a 1-tape reversible Turing machine is computation universaL We give a construction method of a reversible CA which simulates a given 1-tape reversible Turing machine.To do this, we introduce a "one-dimensional partitioned cellular automaton" ( 1-PCA).1-PCA has the property that the local reversibility (i.e., injectivity of a local function) is equivalent to the global reversibility, and thus it facilitates to design a reversible CA.