Cellular Automata/Equivalence Classes


Stephen Wolfram was one of the first to focus on the complete set of CA rules. He observed all the rules that can be created using binary cells   and a three cell neighborhood  . There are   such rules. The number of rules grows exponentially with the number of cell states and even faster with the neighbourhood size. This vast number of rules is a limiting factor when observing the whole set of rules.

Definiton of equivalenceEdit

In this definition a more formal name for rule is used, the local definition function.

The local definition function   is equal to the local definition function  , if and ony if there exists a homomorfism   of global CA states that


Clustering rulesEdit

or different symmetries

  1. input complement
  2. output complement
  3. reflection symmetry
  4. rotation smetry (2D) ?can be produced by reflection no it can not
  5. equivalence class

Equivalence classesEdit


  1. Mirek Wojtowicz, Cellular Automata rules lexicon
  2. Global Dynamics
  3. http://en.wikipedia.org/wiki/Symmetries
  4. http://en.wikipedia.org/wiki/Equivalence_class
  5. http://en.wikipedia.org/wiki/Euclidean_plane_isometry
  6. about xlcau21 (22) http://groups.google.com/group/comp.theory.cell-automata/browse_frm/thread/b4596943ee04f3d6/9fffa47e715ffb7e?q=symmetry&rnum=6&hl=en#9fffa47e715ffb7e