Abstract
In recent years, the notion of complex systems proved to be a very useful concept to define, describe, and study various natural phenomena observed in a vast number of scientific disciplines. Examples of scientific disciplines that highly benefit from this concept range from physics, mathematics, and computer science through biology and medicine as well as economy, to social sciences and psychology. Various techniques were developed to describe natural phenomena observed in these complex systems. Among these are artificial life, evolutionary computation, swarm intelligence, neural networks, parallel computing, cellular automata, and many others. In this text, we focus our attention to one of them, i.e. ‘cellular automata’. We present a truly discrete modelling universe, discrete in time, space, and state: Cellular Automata (CAs) (Sloot & Hoekstra, 2007, Kroc, 2007, Sloot, Chopard & Hoekstra, 2004). It is good to emphasize the importance of CAs in solving certain classes of problems, which are not tractable by other techniques. CAs, despite theirs simplicity, are able to describe and reproduce many complex phenomena that are closely related to processes such as self-organization and emergence, which are often observed within the above mentioned scientific disciplines.
TopBackground
We briefly explain the idea of complex systems and cellular automata and provide references to a number of essential publications in the field.
Complex Systems
The concept of complex systems (CSs) emerged simultaneously and often independently in various scientific disciplines (Fishwick, 2007, Bak, 1996, Resnick, 1997). This could be interpreted as an indication of their universality. Despite the diversity of those fields, there exist a number of common features within all complex systems. Typically a complex system consist of a vast number of simple and locally operating parts, which are mutually interacting and producing a global complex response. Self-organization (Bak, 1996) and emergence, often observed within complex systems, are driven by dissipation of energy and/or information.
Self-organization can be easily explained with ant-colony behavior studies where a vast number of identical processes, called ants, locally interact by physical contact or by using pheromone marked traces. There is no leader providing every ant with information or instructions what it should do. Despite the lack of such a leader or a hierarchy of leaders, ants are able to build complicated ant-colonies, feed their larvae, protect the colony, fight against other colonies, etc. All this is done automatically through a set of simple local interactions among the ants. It is well known that ants are responding on each stimuli by one out of 20 to 40 (depending on ant species) reactions, these are enough to produce the observed complexity.
Emergence is defined as the occurrence of new processes operating at a higher level of abstraction then is the level at which the local rules operate. Each level usually has its own local rules different from rules operating at other levels. An emergent, like an ant-colony, is a product of the process of emergence. There can be a whole hierarchy of emergents, e.g. as in the human body, that consists of chemicals and DNA, going through polypeptides, proteins, cellular infrastructures and cycles, further on to cells and tissues, organs, and bodies. We see that self-organization and emergence are often closely linked to one another.
Cellular Automata
Early development of CAs dates back to A. Turing, S. Ulam, and J. von Neumann. We can define CA’s by four mutually interdependent parts: the lattice and its variables, the neighbourhood, and the local rules (Toffoli & Margolus, 1987, Toffoli, 1984, Vichniac, 1984, Ilachinski, 2001, Wolfram, 2002, Wolfram 1994, Sloot & Hoekstra, 2007, Kroc, 2007). This is briefly explained below.
Key Terms in this Chapter
Small-World Network: A mixture of two different types of connections within each neighbourhood characterizes small-worlds. Typically, a neighbourhood of given vertex is composed of a greater fraction of neighbours having regular short-range connectivity (regular network) and a smaller fraction of random connections (random network). Such type of neighbourhood provides unique properties to each model built on the top of it.
Random Network: A neighbourhood of a vertex is created by a set of randomly chosen links to neighbouring vertices (elements) within a network of vertices.
Complex Network: Most of biological and social networks reflect topological properties not observed within simple networks (regular, random). Two examples are small-world and scale-free networks.
Cellular Automaton: (plural: cellular automata.) A cellular automaton is defined as a lattice (network) of cells (automata) where each automaton contains a set of discrete variables, which are updated according to a local rule operating above neighbours of given cell in discrete time steps. Cellular automata are typically used as simplified but not simple models of complex systems.
Modelling: It is a description of naturally observed phenomena using analytical, numerical, and/or computational methods. Computational modelling is classically used in such fields as, e.g. physics, engineering. Its importance is increasing in other fields such as biology, medicine, sociology, and psychology.
Generalized Cellular Automaton: It is based on use of networks instead of regular lattices.
Emergence: Emergence is defined as the occurrence of new processes operating at a higher level of abstraction then is the level at which the local rules operate. A typical example is an ant colony where this large complex structure emerges through local interactions of ants. For example, a whole hierarchy of emergents exists and operates in a human body. An emergent is the product of an emergence process.
Complex System: A typical complex system consists of a vast number of identical copies of several generic processes, which are operating and interacting only locally or with a limited number of not necessary close neighbours. There is no global leader or controller associated to such systems and the resulting behaviour is usually very complex.
Lattice Gas Automata: Typically, it is a triangular network of vertices interconnected by edges where generalized liquid particles move and undergo collisions. Averaged quantities resulting from such simulations correspond to solutions of the Navier-Stokes equations.
Self-Organized Criticality: A complex system expressing SOC is continuously fed by energy where release of it is discrete and typically occurs in the form of avalanches. Most of its time, SOC operates at a critical point where avalanches occur. Earthquakes and volcano eruptions represent prototypical examples of SOC observed in many naturally observed phenomena.
Regular Lattice: A perfectly regular and uniform neighbourhood for each lattice element called cell characterizes such lattices.
Self-Organization: Self-organization is a process typically occurring within complex systems where a system is continuously fed by energy, which is transformed into a new system state or operational mode by a dissipation of energy and/or information.