Cellular automata

From GenerativeArt

(Difference between revisions)
Jump to: navigation, search
(→Christopher Langton's Lambda)
Current revision (22:14, 18 September 2013) (view source)
(→Christopher Langton's Lambda)
 
-
==Dimensional Cellular Automaton==
+
__FORCETOC__
-
each cell:
+
 
 +
Cellular automata are computational abstractions consisting of cells that compute their state at time t+1 based on the state of the cell and some number of its nearest neighbors at time t. While deceptively simple in their operation, appropriate cellular automata can be shown to be universal computers equivalent to a Turing machine.
 +
 
 +
 
 +
==One Dimensional Cellular Automaton==
 +
 
 +
{{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.
-
===Typical Example:===
 
-
'''Number of rules = number of possible states'''
 
-
* K = 2 (two binary states, 1 and 0).
+
==Example of a Basic Cellular Automaton Rule and Rule Number==
-
* R = 1 (left right neighbors)
+
 
 +
 
 +
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>
-
General case: K<sup>(2R+1)</sup> <br />
+
K<sup>(2R+1)</sup>=2<sup>((2 &times; 1) + 1)</sup>= 2<sup>3</sup> = 8
-
<br />
+
-
2<sup>((2 &times; 1) + 1)</sup>= 2<sup>3</sup> = 8
+
</blockquote>
</blockquote>
-
There are 8 states/rules in the typical example.
+
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.
-
==Numbering Systems==
+
Here is an example of a rule set.
-
# Simply "turn" result on its side:
+
 
-
#: C<sub>i</sub>(T+1) = 01111110 = 124
+
{{SingleImage|imageWidthPlusTen=750|imageURL=http://www.viz.tamu.edu/courses/viza626/10Fall/cellAut1.gif|caption=Rule Set 53}}<br />
-
#: '''"rule number 124"'''
+
 
 +
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>
 +
 
 +
[[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==
==Christopher Langton's Lambda ==
==Christopher Langton's Lambda ==
 +
A statistical measure of phase transition for Wolfram's Classifications.<br />
 +
 +
For all rules: N=K<sup>(2R+1)</sup><br />
 +
 +
(Define) and count the number that will yield a "Quiescent" result.<br />
 +
 +
λ = fraction of states that are not quiescent, i.e. the fraction of states that "result in life"<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 />
 +
{{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==
 +
{{SingleImage|imageWidthPlusTen=510|imageURL=http://www.viz.tamu.edu/courses/viza626/10Fall/cellAut4.gif|caption=VonNeumanNeighborhood}}<br />
 +
{{SingleImage|imageWidthPlusTen=510|imageURL=http://www.viz.tamu.edu/courses/viza626/10Fall/cellAut42.gif|caption=Moore Neighborhood}}<br />
 +
 +
===Simple rules based on totals===
 +
e.g. Conway's Game of Life<br />
 +
{{SingleImage|imageWidthPlusTen=510|imageURL=http://www.viz.tamu.edu/courses/viza626/10Fall/cellAut5.gif|caption=}}<br />
-
lambda = fraction of states that are quiescent<br />
 
-
lambda = N - Nq/N<br />
 
-
e.g. for rule number 124
+
== External Links ==
-
lambda = 8-2/8 = .75
+
[http://www.stephenwolfram.com/publications/recent/nksmain/ An Introduction to Cellular Automata by Stephen Wolfram.]

Current revision

Retrieved from "http://philipgalanter.com/generative_art/wiki/index.php5?title=Cellular_automata"
Personal tools