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.
**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.
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 My favourite is currently out of print but you can still find it second hand: If you want to read a good book on the ideas but at a more academic level try: “ For CAs and biology try: “ 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
First Draft |
|||||

Last Updated ( Saturday, 03 November 2018 ) |