| Cellular Automata - The How and Why |
| Written by Mike James | |||||
| Friday, 26 October 2018 | |||||
Page 4 of 4
Wolfram examined all 256 of the rules by simulating them and discovered that there were four classes of behavior.
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 CAYou 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 nextThere 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 readingA New Computational Universe - Fredkin's SALT CA A Computable Universe - Roger Penrose On Nature As Computation
A Programmers Guide To Theory
|
|||||
| Last Updated ( Saturday, 03 November 2018 ) |
