Cellular Automata

Motto:

Cellular automata are dynamical system where space, time and variables are discrete. Cellular automata are capable of non-numerical simulation of physics, chemistry, biology and others and they are useful for faithful parallel processing of lattice models. In general, they constitute exactly computable models for complex phenomena and large-scale correlations that result from very simple short range interactions.
-- G.Y. Vichniac

General Overview

Cellular automata (CA) were invented by John von Neumann, Stanislav Ulam and Alan Turing in 1940-ies. The very beginning of this theory is associated with development of a general mathematical concept motivated by behaviour of living species. Moreover, later John von Neumann develops the famous self-replicable cellular automaton. It should be emphasized here that CA were reinvented many times in different fields of science.

One of the first applications of CA is related to modelling of propagation of excitation waves in excitable media -- i.e. to the conduction of impulses in a network of connected excitable elements -- published by N. Wiener and A. Rosenblueth. Their model gives the clear theoretical answer on several important -- experimentally long time known -- problems from cardiology.

The number of models in many scientific fields -- ranging from mathematics and physics to biology and social sciences -- based on the CA theory is continuously increasing during last twenty years. This is associated with growing interest of scientists due to increasing computational power of personal computers. Therefore, everybody can use relatively large lattices in CA models. Simulations working with the number of lattice elements -- called cells -- around 10 millions on a mean personal computer is sufficient number for a reliable three-dimensional modelling in many cases.

CA are closely related to Complex Systems. From a certain point of view, one can say that CA are complementary to Complex Systems and vice versa. But it has to be stress out that Complex Systems are much richer. It has been recognized that many complex systems -- that are not solvable by any of classical approaches as for example by sets of ordinary or partial differential equations or by the Monte Carlo simulations -- can be formulated and efficiently solved using CA.

Important Links and Software

The web-page with links to various internet resources related to CAs can be found at the other part of this web page CS & CAs Links. Many links to publicly available software are provided there. Additionally, useful links to pages explaining the basics of the CA theory can be found there as well. I encourage everybody who wishes to know basics of the CA theory to read them. It gives an overview of this theory together with a number of interesting applications in various scientific fields.

For beginners, I recommend to start with the excellent portable CA-environment named Cellular/Cellang designed by Prof. J.D. Eckart. It is composed of a virtual cellular machine named "Cellular" which emulates a parallel environment on a sequential computer. The language named "Cellang" enables formulation of a cellular automaton. Examples of CA-models from various scientific fields are available at that page. It helps to speed up learning process because you can focus your attention to the formulation of a complex problem by CA and not to be lost in the parallelization of a CA-engine.

For more advanced users -- not for beginners -- it could be useful to use their own code that will be probably faster than the general code of Cellular/Cellang. It means that you have to write down your own code of the engine simulating a cellular automaton on a sequential computer and additional code enabling to display simulated data. I recommend to use OpenGL library. It gives a fast and efficient code. I would like to stress out here that it does not mean that Cellular/Cellang is wrong -- definitely not! Please, keep in your mind that Eckart's code is designed as the general and portable code and it performes a perfect work!

Recommended Books

Toffoli T. and Margolus N.: Cellular Automata Theory. The MIT Press, Cambridge, Massachusetts, London, England, 1987.
Weimar J.R.: Simulation with Cellular Automata. Logos Verlag Berlin, Berlin, 1997.
Cellular Automata and Modelling of Complex Systems. (eds. Manevile P., Boccara N., Vichniac G.Y., and Bidaux R.) Springer Verlag, Berlin, Heidelberg, New York, 1989.
Stephen Wolfram, "A New Kind of Science", Wolfram Media Inc., Champaign, 2002. (now available in the on-line version)
Wolfram S.: Cellular Automata and Complexity. Collected Papers. Addison-Wesley Publishing Company, New York, 1994.

Advanced Books: