Emergence, Locating and Measuring It - Systematic Design for Emergence in Cellular Nonlinear Networks - page 50

U>1 but not very large (the “speed of light” limit 1 ), as is the case in Fig. 4.1e).
The “speed of light” in this case is 2 cells/iteration, as follows from the observa-
tion of a “wave front” starting from the middle (position 50) and reaching the left
side of the CA after 25 iterations.
As seen in Fig. 4.1c, an initial growth which is rather slow (U near 1 but much
smaller than the “speed of light”) is a precondition for the birth of gliders.
Why are these gliders so important? For the simple reason that by their interac-
tion one may establish a correspondence between basic computational elements of
classic computers (such as AND, NOT and OR gates) and properly designed and
positioned gliders in a CA. Such behaviors may allow to translate any complex
logic diagram (including that of a universal Turing machine) into a spatial initial
distribution of gliders as an initial state. Consequently the resulting cellular auto-
mata can be proved to behave as a universal computer. This is basically the idea
used in many proofs aiming to demonstrate that various CA can perform universal
computation [71]. Among the most investigated (with a rich repertoire of gliders)
is the “Game of Life” [23].
Of course not all gliders can be combined in such a way as to demonstrate uni-
versal computation, therefore the presence of gliders per se is not a necessary and
sufficient condition for universal computation. Still, their presence is a signature
for complex emergent behaviors.
Let now consider in Fig. 4.2 other examples, chosen from what Wolfram pro-
poses as Class II. In all these cases the CAs are evolving towards a non-
homogeneous equilibrium state (as in Fig. 4.2a or d, where some cells are in a stable
state, different from that of the majority of cells) or towards a low periodic
state as in Fig. 4.2b or c (where a homogeneous state for all cells alternates with
period 2), or towards a nonhomogeneous periodic state as in Fig. 4.2e,f. Again it is
clear that there are many different types of complexities, which may be better dis-
criminated using the measures just mentioned before. As in the case of Class I,
long transients are often associated with gliders and complexity and also with mo-
derate speeds (or exponents of growth) of the wave front generated by the coherent
pattern of the 11 initially random bits (with U ranging from just above 1, as in
Fig. 4.2b, to larger values as in Fig. 4.2d and even larger as in Fig. 4.2c,e but not as
larger as the “speed of light” as seen in Fig. 4.2f ).
The gliders in Fig. 4.2e are among the most interesting since the result of their
collision is not an annihilation process but rather the birth process of two new
other gliders. As seen later, the clustering coefficient C which measures the degree
of order in the final state ranges from close to 1 (indicating a “low frequency” order)
as in most cases displayed in Fig. 4.2, to 0 (indicating a “high frequency” order) as
in Fig. 4.2f ).
1 The “speed of light” in a cellular universe is measured in cells/iterations and its value is
determined by the neighborhood radius. For instance, in a “1s9” CA, the radius, and con-
sequently the “speed of light” is 3 because there are 3 cells to the left and therefore, there
may be circumstances when in the next iteration a certain pattern may propagate 3 cells.
to the left (or right). In a “2s9” CA, the speed of light is only 1 because the neighborhood
is formed only by a “sheet” of 1 cell size around the central cell.