Cellular Automata/Applications of Cellular Automata

The idea that pushed von Neumann to propose the cellular automata model, was constructing a self replicating machine, which components would obey physical laws defined by differential equations. His machine was constructed from approximately 200000 cells, each holding 29 different states. It diverged from physical laws and was so complex that was fully simulated on a computer only in 1989 (by Signorini) but the idea was born.

Cellular automata are now used to model several phenomena present in the physical world. Some models can only be used to express a basic idea of a phenomenon, others are accurate enough to be used for prediction.

Real world phenomena that can be observed in cellular automata edit

Stephen Wolfram (1983) describes CA as:

"Cellular automata are sufficiently simple to allow detailed mathematical analysis, yet sufficiently complex to exhibit a wide variety of complicated phenomena."

He intensively investigated the phenomenology of simple discrete dynamic systems in his book A New Kind of Science (a very Wolfram-centric book, not really useful for serious scientific learning).

Let us just list some examples of physical phenomena and CA that exhibit similar behavior:

  • Patterns on sea shells Cymbiola innexa are similar to patterns generated by rule 30 1D CA
  • Growth of crystals especially patterns in snowflakes can be modeled by simple 2D CA
  • Excitable media in biology (predator-prey dynamics) and chemistry (Belousov-Zhabotinsky reaction) produce spiral patterns that can be seen in Greenberg-Hastings Models
  • Self-replication is seen in the Langton loop (which is a small component of a simplified version of the original von Neumann self-replicating machine)
  • Evolution (self-replication + mutation + selection) can be seen on the Evoloop model, a modified Langton loop
  • Fractal growth of biological organisms
  • Models of universal computation include rule 110 and the Game of Life
  • The Game of Life exhibits interesting patterns that can't really be seen in the real world but they excite our imagination about what CA are capable of

Models with prediction power for physical phenomena edit

Traditionally physical systems are described with differential equations. We use the top down approach, differential equations are discretized to difference systems that are simulated on a computer. There is a centuries long tradition of algebraic methods for the top down approach.

On the other hand CA models must be constructed using a bottom up approach, simple discrete systems must be modified to exhibit the same behavior as described by differential equations. Only recently with the popularization of computers we started researching algebraic methods for the bottom up approach.

Because of this not many models based on cellular automata really grew over the phenomenon hype to a useful tool.

  • Lattice-gas cellular automata and Lattice Boltzmann models for modeling fluid dynamics, there are analytical methods that describe how such system can be constructed to exhibit behavior described by differential equations
  • Stochastic cellular automata can model many physical phenomena, their probabilistic parameters can be adopted to a problem using evolutionary algorithms or machine learning THEE

References edit

CA phenomenology
  1. Wolfram, Stephen, A New Kind of Science. Wolfram Media, Inc., May 14, 2002. ISBN 1579550088
  2. Toffoli T., Margolus N., Cellular Automata Machines: A New Environment for Modeling, The MIT Press (1987), Cambridge, Massachusetts
  3. Hiroki Sayama Structurally Dissolvable Self-Reproducing Loop & Evoloop: Evolving SDSR Loop