Logo image
Se connecter
5-State Rotation-Symmetric Number-Conserving Cellular Automata are not Strongly Universal
Acte de colloque

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

Katsunobu Imai, Hisamichi Ishizaka et Victor Poupet
20th International Workshop on Cellular Automata and Discrete Complex Systems, Vol.LNCS(8996), pp.31-43
AUTOMATA (Himeji, Japan, 07/07/2014–09/07/2014)
2015

Résumé

Universalité Automates cellulaires
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.

Fichiers et liens (1)

url
Find in HALAfficher

Indicateurs

1 Consultations de la notice

Détails

Logo image