Cellular Automata/Equivalence Classes

From Wikibooks, open books for an open world
Jump to: navigation, search

Introduction[edit]

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 k=2 and a three cell neighborhood m=2. There are k^{k^m}=2^{2^3}=256 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 equivalence[edit]

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

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

f_1  f_2

Clustering rules[edit]

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 classes[edit]

References[edit]

  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

mix[edit]