1. Here is one physicist's view of the relevant definitions:
A cellular automaton is a discrete dynamical system. Space, time, and the states of the system are discrete. Each point in a regular spatial lattice, called a cell, can have any one of a finite number of states. The states of the cells in the lattice are updated according to a local rule. That is, the state of a cell at a given time depends only on its own state one time step previously, and the states of its nearby neighbours at the previous time step. All cells on the lattice are updated synchronously. Thus the state of the entire lattice advances in discrete time steps.
2. Here is one mathematician's view of the relevant definitions:
Conventions d=dimension, k=states per site, r=radius (all explained below).
For simplicity, assume d=1 for the moment.
A d-dimensional cellular automaton takes as its underlying space the lattice
SZ> (Z=integers, infinite in both positive and negative directions) where S is a finite set of k elements. The dynamics are determined by a global functionF : SZ ® SZ (1)
whose dynamics are determined ``locally'' as defined below.
A ``local (or neighborhood) function'' f is defined on a finite region
f : S2r+1 ® S (2)
The all-important property of cellular automata, is that this function is determined by a finite lookup table. Both the domain and range of f are finite.
The global function F arises from f by defining:
F(c)i = f(ci-r,…..,ci+r) (3)
A concrete example with k=2,r=1 would take a doubly infinite string of zeroes and ones to a new string at which each site is replaced by the logical and of its two neighbors (Wolfram's elementary rule 90).
Some relevant facts from a topological standpoint are:
1. The base space
SZ is compact and the global function F is continuous.To insert an editorial comment, this makes CA an ideal meeting point between continuous dynamics and complexity theory, since they are discretely defined but exhibit continuous dynamics.
2. The map F commutes with the shift operator which takes
ci to ci+1.In fact cellular automata are characterized completely by properties 1) and 2).
The transition to more dimensions is straightforward. The only difference is that the global function F is defined over
(SZ)d (functions from a d-dimensional lattice to S) and the local function f is determined by enumerating the image of all patches of size (2r+1)d.3. Examples of application fields.
Use of CA in: Physics, Biology, Computer Science, Sociology, Artificial Life.
The COLOMBO’s view of Cellular Automata (CA)
While in the past it was possible to investigate the behaviour of many complex phenomena only in particular cases, the developments in computing have allowed to enlarge the set of cases which can be carefully simulated. In particular, parallel computing is particularly interesting either for reasons of absolute performance or for reasons of cost/performance ratio; extending the range of its effective applicability is therefore an important task. In this paper we will discuss some cases where a model well suited for parallel computing, namely that of Cellular Automata, represents an interesting alternative to classical differential equations methods for modelling complex natural phenomena [19].
CA describe systems whose global evolution may be exclusively described on the basis of local interactions of their constituent parts [2, 23] (Petitot [15] calls this property acentrism). Their computational universality [18] as well as many aspects of modelling have been widely investigated from a theoretical viewpoint [13, 21]. Furthermore CA are easily and naturally implementable on parallel computers and effectively exploit the power of parallelism.
Associating parallelism with acentrism, CA were one of the first Parallel Computing models. Conceived in the 1950's to investigate self-reproduction [22], CA have been used mainly for studying parallel computing methods and the formal properties of model systems [2]. However, during the 1980's, it has been shown that CA are effective in modelling physical systems, in particular fluid dynamics [12, 20].
The kind of phenomena we faced with in the COLOMBO Project can be modelled by CA which have a larger number of states in comparison with the most widely used CA models, like e.g. lattice gases (a feature which is similar in some respects to lattice-Boltzmann models [17]); an empirical method emerged in those works and a parallel computing environment was developed for this type of applications [5, 7]
We introduce here a definition which refers to the main class of CA, i.e. the homogeneous CA, which are widely used in modelling and simulation. Extensions need sometimes to be introduced, e.g. in order to deal with the boundaries of finite physical systems; a discussion can be found in [9].
A homogeneous CA can be intuitively considered as a d-dimensional Euclidean space, the cellular space, partitioned into cells of uniform size (e.g. with a square, cubic, hypercubic tessellation according to the dimension); to each cell an identical finite automaton, the so called elementary automaton (ea), is associated. Input for each ea is given by the states of the ea of the neighbouring cells, where neighbourhood conditions are determined by a pattern invariant in time and constant over the cells. At the time
t=0, ea are in arbitrary states and the CA evolves changing the state of all ea simultaneously at discrete times, according to the transition function of the ea.Formally a CA
A is a quadruple A = <Zd, X, S, s>, whereC={c|c:Zd®S} is the set of possible state assignments to A and will be called the set of configurations; c(i) is the state of cell i. Let c(N(X,i)) be the ordered set of states of the neighbourhood of i. Then the global transition function t is defined by
t:
C ®C a [t(c)](i) = s(c(N(X,i)))It is to be noticed that when appropriate, the previous definition may be easily extended to to different tessellations, e.g., hexagonal, triangular tessellation in a two-dimensional space, which can be easily reduced to the square one.
When natural macroscopic phenomena are considered, the cell corresponds usually to a portion of space: it is therefore natural to assume that the cellular space is at most three dimensional, as in some cases symmetry or homogeneity considerations allow a reduction to two or one dimensions.
Although CA are inspired by acentrism, two global parameters must always be defined: the size of the cell and the clock of the CA transition. Their choice deeply affects the form of the model, as they relate to the choice of a particular space-time scale.
The relevant state variables correspond to substates, and the permitted values of each substate belong to a finite set; continuous quantities might be approximated by discretizing them.
The set of possible states of the cell is given by the Cartesian product of the sets of substates, so
Q = Q1 ´ Q2 ´ ....... ´ Qn, when n substates are considered. It could be useful in some cases to resort to a higher hierarchy, further dividing a substate in sub-substates.The values of the substates are constant in the space occupied by the cell.
The change of each substate in the cell can be caused by internal transformations
T1, T2, ... Tp and/or interactions with the neighbourhood I1, I2, ... , Iq.Internal transformations are defined as the changes in the values of the substates due only to interactions among substates inside the cell or due simply to the elapsing of the time (e.g. water loss by evaporation). That is, internal transformation are those which would take place if all the cells were independent of each other.
An advantage of internal transformations is that, due to the regular geometry of the cell, complicated evolution rules may often be simplified to manageable expressions.
A function
sTi:STi1® STi2 is defined for each internal transition Ti, 1£ i£ p, where STi1,STi2Î Ã ( Q), which is the power set of Q.The interactions with the cells belonging to the neighbourhood (local interactions) are described in terms of flows; in many interesting cases, this leads to the flow of some conserved quantity in the central cell towards or from its neighbours in order to reach equilibrium conditions, with an appropriate relaxation rate. Although this case can look very restrictive, in many cases the problem can be reduced to the minimisation of the differences of a certain quantity in the neighbourhood. The next section illustrates the algorithm adopted for the minimisation of the differences.
When this law is applied, the extent of non equilibrium conditions will be reduced. At each time step, the relaxation rate and the size of the CA time step must be properly chosen in order to describe the actual relaxations kinetics of the macroscopic system.
A function
sIj:SIj1m ® SIj2 is defined for each interaction Ij, 1£ j£ q, where SIj1,SIj2Î Ã (Q), the correspondent relaxation rates rj are also fixed.It is assumed here that the whole phenomenon can be described by sequentially calculating internal transformations and local interactions. This assumption is critic as it cannot generally be justified a priori, and it should be tested in the model validation phase; it often turns out to be justified only in a specific range of conditions.
Another solution would be completely parallel: starting from the values of the substates at the time
t; computing for each substate Qk the variations D k1, D k2, ..... D kp, determined by the transformations and the flows fk1, fk2, ..... fkq, determined by the interactions; adding all the variations in order to obtain the new value of Qk at the time t+1. This last solution is depending on the values of the relaxation rates; inappropriate relaxation rates can give rise to big variations and subsequent inconsistency results, when the outflows are larger than the cell content.References: