Cellular Automata/Equivalence Classes

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

Introduction[edit | edit source]

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 equivalence[edit | edit source]

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 rules[edit | edit source]

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 | edit source]

References[edit | edit source]

  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 | edit source]