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

variances of entropies (called input entropy [73]) were determined to classify
automatically the behavior of cellular automata. Our variance measure is simply
determined as Var , i.e. it is actually the admissible variance computed as

above. As we will see later, the two measures Tr and

'

Var complement each
other and can be used to compose a synthetic and powerful indicator of complex-
ity Cplx capable to predict the occurrence of gliders and complex behaviors with a
high probability.
In comparison to Wuensche's input entropy and its variance, the measures pro-
posed above have the advantage of a smaller computational complexity. Note that
for each CA iteration, the largest computational time is allocate to the diffusive fil-

'

tering in (4.3). The complexity of this equation is of the same order of magnitude as

the complexity of updating all cells in the CA. Therefore, an overall computational
complexity of no more than 2-3 times larger the time used to run the CA without

estimating the measures for emergence is expected. Moreover, (4.3), which may be

regarded as a one-step simulation of a derivate CA, may be easily executed on the
same fast parallel hardware used to simulate the CA. On the opposite, the algo-
rithm to compute the input entropy is sequential in nature and would require more
computational resources for the same number of cells. Also, long transients that
are often mentioned in literature as a sign of complexity are not exactly measured
using the input entropy but rather postulated to be in a direct dependence to large
variances of it. As we will see later, the two measures Var and Tr are rather or-
thogonal and a better measure of complexity can be defined as a linear combina-
tion of them.

function [trans, clus, tzf, delta]=compute_complex(C)
% Usage: [Tr, clus, tzf, var]=compute_complex(C);
% input data is the temporal sequence of
% the clustering index
% tzf is the filtered version of it,
% Tr, clus, and var are parameters used to estimate
% complexity
%---------------------------------------------------
steps=size(C,2);
tzf=filter(ones(1,10),1,C)/10;
% in the above, the C sequence is filtered
delta=0.001+8*sqrt(var(tzf(round(0.8*steps):steps)));
% in the above the variance is determined
% for the last 20% time of CA run
en=tzf(steps);
% end value to be compared with previous
% in order to determine the transient
trans=steps;
while (abs(en-tzf(trans))<delta) & (trans>1)
trans=trans-1;
end
clus=mean(tzf(trans:steps));