# Cellular Automata/Equivalence Classes

## Introduction

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 ${\displaystyle k=2}$ and a three cell neighborhood ${\displaystyle m=2}$. There are ${\displaystyle 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

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

The local definition function ${\displaystyle f_{1}}$ is equal to the local definition function ${\displaystyle f_{2}}$, if and ony if there exists a homomorfism ${\displaystyle g}$ of global CA states that

${\displaystyle f_{1}f_{2}}$

## Clustering rules

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