View source

From GenerativeArt

__FORCETOC__ 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. 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. The basic Wolfram cellular automaton uses only K = 2 states and R = 1 neighbor to either side. ==Example of a Basic Cellular Automaton Rule and Rule Number== 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> K^(2R+1)=2^{((2 &times; 1) + 1)}= 2³ = 8 </blockquote> There are eight possible transitions. <br /> Therefore there are 2⁸ = 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₂ = 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^(2R+1) <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== * Class I - Every cell froze to same state **similar to a halted program **similar to fixed point attractor * Class II - cycle of fixed number of states **similar to infinite loop **similar to limit cycle *Class III - a periodic and semi-random **similar to pseudorandom number set **similar to strange attractor chaotic dynamics *Class IV - complex patterns **similar to [[Artificial life & collective behavior|a-life]] **dynamics on the edge of chaos <blockquote>Note:Because a '''CA''' is a finite state machine it will always eventually repeat... but the state space is huge.</blockquote> ==Christopher Langton's Lambda == A statistical measure of phase transition for Wolfram's Classifications.<br /> For all rules: N=K^(2R+1)<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^(2R+1) <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^(2R+1) = 2^((2*1)+1) = 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 /> == External Links == [http://www.stephenwolfram.com/publications/recent/nksmain/ An Introduction to Cellular Automata by Stephen Wolfram.]

• Template:SingleImage

Return to Cellular automata.