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

From MaRDI portal
scientific article
Language Label Description Also known as
English
Computation-universality of one-dimensional one-way reversible cellular automata
scientific article

    Statements

    Computation-universality of one-dimensional one-way reversible cellular automata (English)
    0 references
    0 references
    16 January 1993
    0 references
    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.
    0 references
    reversible cellular automata
    0 references
    partitioned cellcular automaton
    0 references
    three neighbor-RPCA
    0 references
    computation-universality
    0 references
    two-neighbor RCA
    0 references

    Identifiers