Cellular Automata - The How and Why
Written by Mike James   
Article Index
Cellular Automata - The How and Why
Life and beyond
One-dimensional CAs

One dimension

The problem with two-dimensional CAs, like the one described above and like Life, is that they are just too complicated to analyse in detail.

The solution came from the mathematician Stephen Wolfram, whose first important contribution to the theory was to reduce the situation to the point where it could be analysed. He decided that a one-dimensional CA would be worth investigating.

The idea of a 1D CA is no different from a 2D one but we start off with a line of agents and at the next tick the line is replaced by a new line determined by the rule that is being followed.

As this is only a 1D arrangement we don’t actually have to replace the existing line, just display the new line underneath, so building up a complete pattern of the development of the CA. It’s also possible to specify the rule in terms of the color of the agent, its two neighbors and the color of the new cell just below.

For example the pattern:

 

fig3

 

specifies a rule that if an agent is white and has two black neighbors then the cell below should be black.

As there are only eight possible arrangements of neighbors a complete rule that specifies exactly what should happen in any situation only has to list if the result of each of the eight is black or white.

By thinking of black as 1 and white as 0 you can give each neighbor pattern a number between 0 and 7 and then read off the resulting black or white cell on the next row as a set of eight zeros or ones, i.e. a binary number. This can be used as an index to specify the rule.

fig4

This means you can refer to any of the 256 rules that are possible in a 1D CA by number. This in itself is something of a conceptual breakthrough because now you can begin to think about classifying the behavior of each of the possible rules.

This is exactly what a biologist would do when confronted by a new biosphere. Once you have classified what you are looking at you can start to see patterns and make theories up about what you are looking at.

Without classification you are simply looking at an undifferentiated mess, no matter how interesting it might appear.

Wolfram examined all 256 of the rules by simulating them and discovered that there were four classes of behavior.

 

  • Class 1 behaviors were boring, just resulting in all on or all off states.
  • Those in Class 2 were also fairly boring and resulted in stable states, only slightly more interesting than Class 1.
  • Class 3 produced disordered behavior – random triangles and “video noise”.
  • Finally Class 4 displayed complex behaviors that included “Life-like” patterns. Class 4 patterns demonstrate that even 1D CAs have enough complexity to produce interesting behavior.

 

rule90

Rule 90 looks to produce a nice regular pattern so its in Class 4.

Many of these 1D CAs produce interesting patterns and they are fun to play with. Not quite as impressive as fractals from a graphics point of view but given the amount you put in you seem to get a lot out – and of course this is the point!

Even 1D CAs are complex enough to make you belive that complexity can arrise easily from simplicity. In fact rule 30 has been proposed as a cryptographic method. The one way function is just the evolution of an inital state - the message It can't be cracked because it is very hard to work backward from a final configuration to the initial configuration that created it.

Generalized CA

You can invent your own type of CA - you can vary the form of the grid, the states that the cells can have and the rules that apply. You can work in more than 2D if you want to but this is proving to be more difficult than you might expect.

Also of interest are probablisitc CAs where the update rule specifies a probablity of a state change.

One important class of CAs are reversible. If there is a one-to-one correspondence between intial and final configurations. Such CA are in a sense deterministic and are generally used to model physical systems. A reversable system obeys the second law of thermodynamics and neither creates nor destroys information. Not all CAs are reversible and many have states that can never be reached from a starting configuration - such things are very hard to prove however.

Today's research in CAs is very broad and includes work to find new configurations in Life that do interesting things, to find 3D CAs that have specific physical properties and to breed CAs using the genetic algorihm.

Perhaps the most important thing to realize is that CAs are a model for distributed parallel processing that might just be easier to work with than things like map/reduce and Hadoop. If you find this surpsizing consder the fact that a spreadsheet is a programable CA we each cell can have its own rule.  CAs with fixed rules are a modle for Single Instruction Multple Data (SIMD) parallelisem. CAs with variable rules are a model for Multiple Instruction Multiple Data (MIMD) parallelism .

Where next

There are far too many books, papers and websites even on CAs to give even a reasonably full list.

While A New Kind of Science is the best known of the books proposing that CAs might be a theory of everything, it’s a shame not to ignore some of the really good alternatives, links to all of which are in the right-hand panel above.

My favourite is currently out of print but you can still find it second hand: “Enter the Complexity Lab: Where Chaos Meets Complexity”, by William Roetzheim. Any of the many popular science books with words like “Complexity”, “Chaos”, or “Artificial Life” in the title are also worth looking at.

If you want to read a good book on the ideas but at a more academic level try: “Nonlinear Physics for Beginners: Fractals, Chaos, Pattern Formation, Solitons, Cellular Automata and Complex Systems”  by Lui Lam.

For CAs and biology try: “Modeling Nature: Cellular Automata Simulations with Mathematica” by R.J. Gaylord & K. Nishidate.

If you just want some software to play with then download Cellab, and lots of other interesting software, from:

www.mathcs.sjsu.edu/faculty/rucker/

 

Related reading

A New Computational Universe - Fredkin's SALT CA

A Computable Universe - Roger Penrose On Nature As Computation

A New Kind of Science Is Ten

Spreadsheets are special

Life in Silverlight 4

Life in WPF

It's life but not ...

Brain-like computing?

 

blog comments powered by Disqus

 

To be informed about new articles on I Programmer, subscribe to the RSS feed, follow us on Google+, Twitter, Linkedin or Facebook, install the I Programmer Toolbar or sign up for our weekly newsletter.

<ASIN:1579550088>

<ASIN: 0672303957>

<ASIN:9810201419>

<ASIN:0387946209>

<ASIN: 0262581116 >

 



 
 

   
RSS feed of all content
I Programmer - full contents
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.