On Local Symmetries And Universality In Cellular Autmata

Details On Local Symmetries And Universality In Cellular Autmata On Local Symmetries And Universality In Cellular Autmata

2009-02-07

arxiv.org/abs/0902.1253v1

26th International Symposium on Theoretical Aspects of Computer Science STACS 2009 (2009) 195-206

Computer Science

Discrete Mathematics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On Local Symmetries And Universality In Cellular Autmata does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Local Symmetries And Universality In Cellular Autmata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Local Symmetries And Universality In Cellular Autmata will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-312160