Hunter Snevily
United States
Registered: Dec 2009
Posts: 3 
CAs ?'s based on set theory properties
What properties do ‘ideal based’ cellular automata have?
B=black W=white
Consider rule 31
BBB BBW BWB BWW WBB WBW WWB WWW 3 previous cells
W W W B B B B B center cell
Each three cell arrangement can be thought of as a set where Bmember of and WNOT a member of, so
BBB= {1,2,3}, BWB={1,3}, WWW=empty set, etc.
The three cell arrangements of rule 31 with center cell colored black form an ideal I.
Def An ideal I is a collection of subsets of a finite set X that are closed under the subset operator – so if A is in I and B is a subset of A than B is in I.
The ideal I associated with rule 31 is
I={empty set, {1},{2},{3},{2,3}}
Now consider rule 34
BBB BBW BWB BWW WBB WBW WWB WWW 3 previous cells
W W B W W W B W center cell
The three cell arrangements of rule 34 with center cell colored black do not form an ideal since { {1.3}.{3}} is not closed with respect to taking subsets.
We call rule 31 an ideal based CA – rule 34 is NOT an ideal based CA.
What properties do ‘ideal based’ cellular automata have?
A kuniform ideal of a finite set X consists of all subsets of X of size k or less.
Rule 23
BBB BBW BWB BWW WBB WBW WWB WWW 3 previous cells
W W W B W B B B center cells
Rule 23 is a 1uniform ‘ideal based’ cellular automata.
ARE all kuniform CA periodic = Class II (Wolfram’s classification)?
Now a host of questions arise based on the set theoretic properties of the arrangement of cells (in the rule of a CA) whose center cell is colored black.
For example
What properties do ‘union closed’ CA have?
What properties do ‘intersecting’ CA have?
Report this post to a moderator  IP: Logged
