Cellular Automata/Equivalence Classes

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

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

Cellular Automata/Equivalence Classes

Contents

Introduction edit

Definiton of equivalence edit

Clustering rules edit

Equivalence classes edit

References edit

mix edit