Prev: CA as paradigm system
Next: Mean Field Assumption

TODO
  • CLARIFY: last paragraph, what is meant??



Generic Behaviour of Cellular Automata


(Concepts: classification
ca_wolfram.png
The different classes of CA as classified by Wolfram (1984)
of CA models (classes), order parameter, almost all cases (highlighted by exceptions), vanishingly small parameter regimes)

In ODEs/MAPS we can generally distinguish three types of dynamical behaviour, that all systems eventually will result in:
- Fixed points (equilibria)
- Limit cycles
- (deterministic) Chaos
In a similar way one can ask: What does an arbitrary CA do for arbitrary initial conditions? Wolfram (1984) conducted such a study on 1D CAs using random transition rule tables with varying neighbourhoods and found the following classes of CA behaviour (with non-spatial analog in brackets):
  • Class I: to uniform state, all black or all white (fixed state)
  • Class IIa: localized domains (limit cycle)
  • Class IIb: non-localized domains (limit cycle)
  • Class III: non-periodic, non-localized (high dimensional chaos)
  • Class IV: long transient, unpredictable (universal computation)

These classes were defined according to the effect that perturbations have on the behaviour of the system, i.e. what happens to disturbances? In Class I the system returns to the fixed point. In Class II one can change from one attractor to another but the disturbance is limited to the attractor one is in. In Class III disturbances have a non-local impact and percolate throughout the field. This class shows high-dimensional chaos, but its statistical properties have a short transient. In Class IV disturbances can spread or not, die out or not, can be non-local and have a long transient. In other words they are highly unpredictable. Moreover, new entities with their own behaviour and interactions arise which lead to a new level of description and dynamics. Such entities have been suggested to have the capability of universal computation.

Predictions about CAs


In strict sense, it is impossible to predict from the rules in which class a CA will fall. However, for almost all cases, we can predict the class by using Langton (1991)'s ordering parameter lambda: the number of rules which lead to the quiescent state (which is one of the CA states). He defined
modulo_fractal.png
Disturbance in modulo prime percolates as a fractal pattern

lambda = (K^N - Nq) / K^N,
where K is the number of states, N is the number of neighbours and Nq is the number of rules leading to the quiescent state (i.e. the number of times the quiescent state is found in the transistion vector: the vector of all possible outcomes of the next state function). The ordering parameter lambda varies between 0 and (1 - 1/K). Hence, for binary CAs the maximal value of lambda is 0.5.

Using this ordering parameter it becomes clear that as lambda increases one transverses from Class I -- IIa -- IIb- IV - III, where Class IV is b
etween the periodic and chaotic phase and occurs in a vanishingly small parameter region (i.e. a vanishlingly small region of lambda-values). This parameter regime clearly shows very interesting and unpredictable behaviour, but if it is so "rare", is it important to consider?

Let us consider some examples of the use of the ordering parameter lambda:

In Modulo Prime (with p=2), K=2, N=4 and Nq=8 (since half of the 16 possible combinations of the four neighbour states will lead to a next state of 0 (quiescent state). Hence, lambda = (16 - 8) / 16 = 0.5. Hence, according to such ordering Modulo Prime is class III, and is therefore highly disordered and chaotic. In fact this can be illustrated by tracking the percolation of a single pixel change in a given random initial condition. If such a change is tracked in time it displays a fractal pattern which spreads throughout the field.

The Voting rule also has lambda=0.5, because again half of the possible neighbour combinations will lead to a next state of 0. However, this case is not chaotic, although it is maximally disordered. It is therefore Class I in most cases (no noise), and with the addition of noise it becomes Class II. Hence, this is one example of a CA which is an exception to the classification by ordering parameter lambda.

An important point shown here is that generalizations, or model outcomes, are based on almost all cases (i.e. there are exceptions to the rule). These should be seen as special cases which can exist, and an all cases model should be a different model.

Next: Mean Field Assumption


References

Wolfram S (1984) Universality and complexity in Cellular automata. Physica D 10D7-12. DOI
Langton CG (1991) Life at the edge of chaos. In: Artificial life II (eds. Langton et al) pp 41-91 PDF (see also: Bak P, Tang C, and Wiesenfeld K (1988) Selforganized criticality Phys Rev A 38:364-378).



(CHANGELOG 2014-2015)

- In stead of comparing to Kauffmann, we compare behaviour to ODE/MAP behaviour (intro)
- Added: in strict sense it is impossible to predict a class, however...



(NOTES FROM COURSE 2006-2007)

Generic Behaviour of CA's

Similar to Kauffmann one can ask: what does an arbitrary CA do for arbitrary initial conditions? (vs specific CA, specific initial condition)

Wolfram: random initial conditions, random rules.
Class 1: fixed state
Class 2a: localized domains
Class 2b: non-localized domains
Class 3: non-periodic, non-localized (high-D chaos)
Class 4: long transient, unpredictable: need to let it life its life (universal computation).

Classes defined according to perturbations: what happens to disturbances?
1 = back to fixed point
2 = can go to another attractor, difference limited to attractor you are in (localized change)
3

non-local impact > percolation (deterministic chaos special type (HIgh-Dimensional). In logistic


  • non-periodic but mapping in low D space can be quite specific

In CA => H-D space needed to show bounds of states
Statistical properties have short transient.

4 = signal can spread/ or not, diet out/or not, non-local disturbance, long transient.
Game of life: can compute anything.
Choose the right representation can use that to compute anything.

Class 3: high dimensional chaos -> not distinguishable from noise, however there is no difference between a stochastic cellular automata and a deterministic one (i.e. random number generator driving stochasiticity is deterministic, when taken together still fullfill unique next state).


Predictions about CAs

Langton: used a less arbitrary and nice sampling method (ordering parameter).
Nq

number of quiesent states, K states, N

neighbours:

lamba = (K^N - Nq) / K^N.

(For instance take state 0 as quiescent state.). Lamba is defined as the number of rules (out of K^N) in the rule table that go to the non-queiescent state and ranges from 0 to (1-1/K).

Findings: as lamba increases one passes through the classes: I --- IIa --- IIb - IV - III ---
(where Class IV is between the periodic and chaotic phase).

According to such ordering:
Modulo Prime is class III (lamba 0.5) and is therefore highly disordered and chaotic. This can be illustrated by tracking the percolation of a single pixel change in a given initial state through time and this gives a fractal pattern which spreads throughout the field.

Voting rule is also lambda 0.5 but is non-chaotic, but max disordered (?). Is it therefore Class I? In most cases yes. No noise then Class II, with noise Class I. This should be seen as an exception to the random rule generation.

What does this mean about generalizations (model outcomes) based on ALMOST ALL CASES? (i.e. if there are exceptions to the rule?).
One can see exceptions as a special case, which can exist, and an ALL CASES model should be a different model.



[[prebio|]]