Cellular automata
From GenerativeArt
(Difference between revisions)
(→External Links) |
Current revision (22:14, 18 September 2013) (view source) (→Christopher Langton's Lambda) |
||
==Example of a Basic Cellular Automaton Rule and Rule Number== | ==Example of a Basic Cellular Automaton Rule and Rule Number== | ||
- | |||
- | + | In the most basic one dimensional cellular automaton, where: | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | In the most basic one dimensional cellular automaton: | + | |
- | * K = 2 (two | + | * K = 2 (each cell has two states, 1 and 0). |
- | * R = 1 (on neighbor to the left, and one to the right, | + | * R = 1 (the context for each cell includes one on neighbor to the left, and one to the right, wrapping around at the ends) |
<blockquote> | <blockquote> | ||
- | 2<sup>((2 × 1) + 1)</sup>= 2<sup>3</sup> = 8 | + | K<sup>(2R+1)</sup>=2<sup>((2 × 1) + 1)</sup>= 2<sup>3</sup> = 8 |
</blockquote> | </blockquote> | ||
- | + | There are eight possible transitions. <br /> | |
+ | Therefore there are 2<sup>8</sup> = 256 possible rule sets. <br /> | ||
+ | The rule sets can be exhaustively listed by counting, in this case using eight bits. | ||
Here is an example of a rule set. | Here is an example of a rule set. | ||
- | {{SingleImage|imageWidthPlusTen= | + | {{SingleImage|imageWidthPlusTen=750|imageURL=http://www.viz.tamu.edu/courses/viza626/10Fall/cellAut1.gif|caption=Rule Set 53}}<br /> |
The eight result bits can be used to uniquely name the rule set with a rule number. | The eight result bits can be used to uniquely name the rule set with a rule number. | ||
- | + | 00110101<sub>2</sub> = 53 | |
- | thus the set of transitions shown above are called "rule number 53 | + | thus the set of transitions shown above are called "rule number 53" or "rule set number 53" |
+ | |||
+ | For the general case: <br /> <br /> | ||
+ | For each possible combination of state and context, a state for the next time step must be specified. <br /> | ||
+ | |||
+ | Where: | ||
+ | |||
+ | * K = The number of states in each cell | ||
+ | * R = The number of cells to either side that provide context | ||
+ | |||
+ | <blockquote> | ||
+ | the number transitions in a rule set = K<sup>(2R+1)</sup> <br /> | ||
+ | |||
+ | </blockquote> | ||
[[http://philipgalanter.com/howdy/applets/1dca/index.html Click here to run a one dimensional cellular automata applet.]] | [[http://philipgalanter.com/howdy/applets/1dca/index.html Click here to run a one dimensional cellular automata applet.]] | ||
[[http://mathworld.wolfram.com/ElementaryCellularAutomaton.html Click here to access a Wolfram Mathworld page illustrating all 256 rules.]] | [[http://mathworld.wolfram.com/ElementaryCellularAutomaton.html Click here to access a Wolfram Mathworld page illustrating all 256 rules.]] | ||
- | |||
==Wolfram's Classification== | ==Wolfram's Classification== | ||
(Define) and count the number that will yield a "Quiescent" result.<br /> | (Define) and count the number that will yield a "Quiescent" result.<br /> | ||
- | λ = fraction of states that are quiescent<br /> | + | λ = fraction of states that are not quiescent, i.e. the fraction of states that "result in life"<br /> |
- | λ = N - Nq/N<br /> | + | N = K<sup>(2R+1)</sup> <br /> |
+ | Nq = count the number of rules resulting in quiescence<br /> | ||
+ | λ = (N - Nq/N<br /> | ||
e.g. for rule number 124<br /> | e.g. for rule number 124<br /> | ||
{{SingleImage|imageWidthPlusTen=510|imageURL=http://www.viz.tamu.edu/courses/viza626/10Fall/cellAut2.gif|caption=}}<br /> | {{SingleImage|imageWidthPlusTen=510|imageURL=http://www.viz.tamu.edu/courses/viza626/10Fall/cellAut2.gif|caption=}}<br /> | ||
- | + | N = K<sup>(2R+1)</sup> = 2<sup>((2*1)+1)</sup> = 8<br /> | |
- | + | Nq = 2<br /> | |
- | + | λ = ( 8-2 )/8 = .75<br /><br /> | |
+ | {{SingleImage|imageWidthPlusTen=750|imageURL=http://www.viz.tamu.edu/courses/viza626/10Fall/cellAut3.gif|caption=}}<br /> | ||
==Two Dimensional Cellular Automaton== | ==Two Dimensional Cellular Automaton== |