An 8-State Simple Reversible Triangular Cellular Automaton that Exhibits Complex Behavior

Abstract : A three-neighbor triangular partitioned cellular automaton (TPCA) is a CA whose cell is triangular-shaped and divided into three parts. The next state of a cell is determined by the three adjacent parts of its neighbor cells. The framework of TPCA makes it easy to design reversible triangular CAs. Among them, isotropic 8-state (i.e., each part has two states) TPCAs, which are called elementary TPCAs (ETPCAs), are extremely simple, since each of their local transition functions is described by only four local rules. In this paper, we investigate a specific reversible ETPCA ${T}_{0347}$, where 0347 is its identification number in the class of 256 ETPCAs. In spite of the simplicity of the local function and the constraint of reversibility, evolutions of configurations in ${T}_{0347}$ have very rich varieties, and look like those in the Game-of-Life CA to some extent. In particular, a “glider” and “glider guns” exist in ${T}_{0347}$. Furthermore, using gliders to represent signals, we can implement universal reversible logic gates in it. By this, computational universality of ${T}_{0347}$ is derived.
Type de document :
Communication dans un congrès
Matthew Cook; Turlough Neary. 22th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2016, Zurich, Switzerland. Lecture Notes in Computer Science, LNCS-9664, pp.170-184, 2016, Cellular Automata and Discrete Complex Systems. 〈10.1007/978-3-319-39300-1_14〉
Domaine :

Littérature citée [14 références]

https://hal.inria.fr/hal-01435027
Contributeur : Hal Ifip <>
Soumis le : vendredi 13 janvier 2017 - 15:23:51
Dernière modification le : lundi 16 janvier 2017 - 11:02:24
Document(s) archivé(s) le : vendredi 14 avril 2017 - 20:05:44

Fichier

Accès restreint
Fichier visible le : 2019-01-01

Connectez-vous pour demander l'accès au fichier

Citation

Kenichi Morita. An 8-State Simple Reversible Triangular Cellular Automaton that Exhibits Complex Behavior. Matthew Cook; Turlough Neary. 22th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2016, Zurich, Switzerland. Lecture Notes in Computer Science, LNCS-9664, pp.170-184, 2016, Cellular Automata and Discrete Complex Systems. 〈10.1007/978-3-319-39300-1_14〉. 〈hal-01435027〉

Métriques

Consultations de la notice