Computation-universality of one-dimensional one-way reversible cellular automata (Q1198089)

A reversible (or injective) cellular automaton (RCA) is a ``backward deterministic'' CA, i.e., every configuration of it has at most one predecessor. In the one-dimensional case, it has been shown by \textit{K. Morita} and \textit{M. Harao} [Computation universality of one-dimensional reversible (injective) cellular automata, Trans IEICE Japan, 758-762 (1989)] that a three-neighbor RCA is computation-universal. In this paper, we investigate the computing ability of a one-dimensional two- neighbor (i.e., one-way) RCA. We first investigate a one-dimensional partitioned cellular automaton (PCA), a special subclass of a CA, and show that three neighbor-RPCA can be simulated by a two-neighbor RPCA. From this and the previous result that three-neighbor RPCA can simulate a universal Turing machine [Morita and Harao, loc. cit.], computation- universality of a two-neighbor RPCA and a two-neighbor RCA is derived.