Cellular Automata - The How and Why
Written by Mike James   
Friday, 26 October 2018
Article Index
Cellular Automata - The How and Why
Life and Beyond
Gliders
Wolfram's Classification

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 believe that complexity can arise easily from simplicity. In fact rule 30 has been proposed as a cryptographic method. The one way function is just the evolution of an initial 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 probabilistic CAs where the update rule specifies a probability of a state change.

One important class of CAs are reversible. If there is a one-to-one correspondence between initial and final configurations. Such CA are in a sense deterministic and are generally used to model physical systems. A reversible 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 algorithm.

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 surprising consider the fact that a spreadsheet is a programmable CA we each cell can have its own rule.  CAs with fixed rules are a model for Single Instruction Multiple Data (SIMD) parallelism. 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?

 

A Programmers Guide To Theory
First Draft

There is a more recent version of this:

Now available as a paperback and ebook from Amazon.

A Programmers Guide To Theory - NP & Co-NP

theorycover

Contents

  1. What Is Computable?
  2. Finite State Machines
  3. What is a Turing Machine? 
  4. Computational Complexity
  5. Non-computable numbers
  6. The Transfinite
  7. Axiom Of Choice
  8. Lambda Calculus
  9. Grammar and Torture
  10. Reverse Polish Notation - RPN
  11. Introduction to Boolean Logic
  12. Confronting The Unprovable - Gödel And All That
  13. The Programmer's Guide to Fractals
  14. The Programmer's Guide to Chaos*
  15. Prime Numbers And Primality Testing
  16. Cellular Automata - The How and Why
  17. Information Theory
  18. Coding Theory
  19. Kolmogorov Complexity

*To be revised

square

 



 

Comments




or email your comment to: comments@i-programmer.info

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

 

<ASIN:1579550088>

<ASIN: 0672303957>

<ASIN:9810201419>

<ASIN:0387946209>

<ASIN: 0262581116 >

 



Last Updated ( Saturday, 03 November 2018 )