Cellular Automata/Equivalence Classes

From Wikibooks, open books for an open world

Unreviewed changes are displayed on this page

This page may need to be reviewed for quality.

Jump to: navigation, search

[edit] 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 $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.

[edit] Definiton of equivalence

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

[edit] Clustering rules

or different symmetries

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

[edit] Equivalence classes

[edit] References

[edit] mix

Cellular Automata/Equivalence Classes

Contents

[edit] Introduction

[edit] Definiton of equivalence

[edit] Clustering rules

[edit] Equivalence classes

[edit] References

[edit] mix

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

Community

Toolbox

Sister projects

Print/export