Cellular automata
From GenerativeArt
(Difference between revisions)
(spacing) |
Current revision (22:14, 18 September 2013) (view source) (→Christopher Langton's Lambda) |
||
{{SingleImage|imageWidthPlusTen=510|imageURL=http://www.viz.tamu.edu/courses/viza626/10Fall/cellAut1b.gif|caption=}}<br /> | {{SingleImage|imageWidthPlusTen=510|imageURL=http://www.viz.tamu.edu/courses/viza626/10Fall/cellAut1b.gif|caption=}}<br /> | ||
| - | + | ||
| + | Each cell has the same number of possible states: | ||
| + | |||
* K = Number of States. | * K = Number of States. | ||
| - | * R = Number of neighbors | + | |
| + | At each time step the next state is calculated on the basis of the present state of the cell and some number of its nearest neighbors: | ||
| + | |||
| + | * R = Number of neighbors considered to either side | ||
* T = Time step. | * T = Time step. | ||
The basic Wolfram cellular automaton uses only K = 2 states and R = 1 neighbor to either side. | The basic Wolfram cellular automaton uses only K = 2 states and R = 1 neighbor to either side. | ||
| - | |||
| - | |||
| - | * K = 2 (two | + | ==Example of a Basic Cellular Automaton Rule and Rule Number== |
| - | * R = 1 (left right | + | |
| + | |||
| + | In the most basic one dimensional cellular automaton, where: | ||
| + | |||
| + | * K = 2 (each cell has two states, 1 and 0). | ||
| + | * 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> | ||
| - | + | K<sup>(2R+1)</sup>=2<sup>((2 × 1) + 1)</sup>= 2<sup>3</sup> = 8 | |
| - | + | </blockquote> | |
| - | 2<sup>((2 × 1) + 1)</sup>= 2<sup>3</sup> = 8 | + | |
| + | 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. | ||
| + | |||
| + | {{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. | ||
| + | |||
| + | 00110101<sub>2</sub> = 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> | </blockquote> | ||
| - | + | [[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.]] | |
| - | + | ||
| - | + | ||
| - | + | ||
==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 /> | ||
| - | λ = 8-2/8 = .75<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= | + | {{SingleImage|imageWidthPlusTen=750|imageURL=http://www.viz.tamu.edu/courses/viza626/10Fall/cellAut3.gif|caption=}}<br /> |
==Two Dimensional Cellular Automaton== | ==Two Dimensional Cellular Automaton== | ||
e.g. Conway's Game of Life<br /> | e.g. Conway's Game of Life<br /> | ||
{{SingleImage|imageWidthPlusTen=510|imageURL=http://www.viz.tamu.edu/courses/viza626/10Fall/cellAut5.gif|caption=}}<br /> | {{SingleImage|imageWidthPlusTen=510|imageURL=http://www.viz.tamu.edu/courses/viza626/10Fall/cellAut5.gif|caption=}}<br /> | ||
| + | |||
| + | |||
| + | == External Links == | ||
| + | |||
| + | [http://www.stephenwolfram.com/publications/recent/nksmain/ An Introduction to Cellular Automata by Stephen Wolfram.] | ||
