5-State Rotation-Symmetric Number-Conserving Cellular Automata are not Strongly Universal

Katsunobu Imai 1 Hisamichi Ishizaka 1 Victor Poupet 2
2 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We study two-dimensional rotation-symmetric number- conserving cellular automata working on the von Neumann neighborhood (RNCA). It is known that such automata with 4 states or less are trivial, so we investigate the possible rules with 5 states. We give a full characterization of these automata and show that they cannot be strongly Turing universal. However, we give example of constructions that allow to embed some boolean circuit elements in a 5-states RNCA.
Type de document :
Communication dans un congrès
AUTOMATA, Jul 2014, Himeji, Japan. 20th International Workshop on Cellular Automata and Discrete Complex Systems, LNCS (8996), pp.31-43, 2015, 〈http://www.eng.u-hyogo.ac.jp/eecs/eecs12/automata2014/〉. 〈10.1007/978-3-319-18812-6_3〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01476796
Contributeur : Victor Poupet <>
Soumis le : samedi 25 février 2017 - 19:39:45
Dernière modification le : lundi 16 juillet 2018 - 16:24:02

Lien texte intégral

Identifiants

Collections

Citation

Katsunobu Imai, Hisamichi Ishizaka, Victor Poupet. 5-State Rotation-Symmetric Number-Conserving Cellular Automata are not Strongly Universal. AUTOMATA, Jul 2014, Himeji, Japan. 20th International Workshop on Cellular Automata and Discrete Complex Systems, LNCS (8996), pp.31-43, 2015, 〈http://www.eng.u-hyogo.ac.jp/eecs/eecs12/automata2014/〉. 〈10.1007/978-3-319-18812-6_3〉. 〈lirmm-01476796〉

Partager

Métriques

Consultations de la notice

88