On Local Symmetries and Universality in Cellular Automata

Abstract : Cellular automata (CA) are dynamical systems defined by a finite local rule but they are studied for their global dynamics. They can exhibit a wide range of complex behaviours and a celebrated result is the existence of (intrinsically) universal CA, that is CA able to fully simulate any other CA. In this paper, we show that the asymptotic density of universal cellular automata is 1 in several families of CA defined by local symmetries. We extend results previously established for captive cellular automata in two significant ways. First, our results apply to well-known families of CA (e.g. the family of outer-totalistic CA containing the Game of Life) and, second, we obtain such density results with both increasing number of states and increasing neighbourhood. Moreover, thanks to universality-preserving encodings, we show that the universality problem remains undecidable in some of those families.
Document type :
Conference papers
Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.195-206, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00359174
Contributor : Publications Loria <>
Submitted on : Friday, February 6, 2009 - 10:58:12 AM
Last modification on : Monday, March 21, 2016 - 5:34:49 PM
Document(s) archivé(s) le : Tuesday, June 8, 2010 - 9:57:25 PM

Files

Boyer_new.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00359174, version 1
  • ARXIV : 0902.1253

Collections

Citation

Laurent Boyer, Guillaume Theyssier. On Local Symmetries and Universality in Cellular Automata. Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.195-206, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00359174〉

Share

Metrics

Record views

152

Document downloads

112