Computation-universality of one-dimensional one-way reversible cellular automata (Q1198089): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Logical Reversibility of Computation / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Conservative logic / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3677179 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Computation and construction universality of reversible cellular automata / rank | |||
Normal rank |
Revision as of 15:36, 16 May 2024
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
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