A New Kind of Science: The NKS Forum > Pure NKS > CAs ?'s based on set theory properties
Author
 Thread
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 B-member of and W-NOT 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 k-uniform 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 1-uniform ‘ideal based’ cellular automata.

ARE all k-uniform 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

12-09-2009 09:01 PM
mdmd

Registered: Not Yet
Posts: N/A

Thank you for this important information , nice post

Report this post to a moderator | IP: Logged

07-05-2010 09:17 AM

wolframscience.com  |  wolfram atlas  |  NKS online  |  Wolfram|Alpha  |  Wolfram Science Summer School  |  web resources  |  contact us

Forum Sponsored by Wolfram Research

© 2004-15 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer | Archives