Now, a simulation of a system which arrives at a given result, and the information contained in the intermediate steps of such a simulation, clearly comprise some form of explanation, which will indeed be very useful to explain some phenomena. If developed in an external fashion, it at least demonstrates sufficient understanding of the original system so as to be able to reproduce its behaviour. This is clearly an important step.
To return to our motivating quotation, however, surely if we really
understand a system, we shouldn't need to perform such a simulation. We
would understand both the circumstances which are necessary for each
relevant phenomenon to arise, and the correlation between the initial state
and such circumstances. We could then say, directly, whether and why
or
will happen.
There is clearly a continuum of levels of difficulty and complexity of analysis. One property of a system will be the minimum level of analysis to which it will yield. To couch this in computational terms, there is a minimum amount of computation which needs to be carried out to predict any given phenomenon. With this in mind, I propose the following definition, which will be made more mathematically precise in the forthcoming sections:
What we mean by a `prediction' is left deliberately vague - it may be precisely quantitative or just a loose classification. With that proviso, rather than phrasing this definition as a hypothesis about our concept of `emergence', I prefer to use it as a formalisation of the term `emergent' in the discussion which follows. I seek to demonstrate the viability of the above definition as an axiom in the study of emergence in complex adaptive systems. Note that I have yet to demonstrate the existence of emergence.
Emergence as I describe it here has been loosely termed `computational emergence' by [4]. However, abstract computer simulations have been used ever more frequently to gain an understanding of physical phenomena[7][13] and in the evolution of specific functionality[9]. So computational emergence can, I feel, bear upon Cariani's `thermodynamic emergence' and `emergence relative to a model'.
So, emergent phenomena are those for which the amount of computation
necessary for prediction from an optimal set of rules, classifications
and analysis, even derived from an idealised perfect understanding, can
never improve upon the amount of computation necessary to simulate the
system directly from our knowledge of the rules of its interactions. I
posit that this definition concurs with the wishy-washy heuristic sense
people mean when they (ab)use such terms as `emergent behaviour' and
`emergent complexity'
.
Firstly note that the predictive difficulty of a phenomenon will depend
upon both the size, , and the interaction complexity of a given member
of a family of complex systems.
I argue that there is no discontinuous separation between emergence and non-emergence. Emergence is purely the result of a phase change in the amount of computation necessary for optimal prediction of certain phenomena. To explain this phase change, we need to look at the two means of prediction we can use:
Let
be the amount of computation required to simulate a
system, and arrive at a prediction of the given phenomenon. At times we
may wish to consider this an idealised quantity referring to the optimally
tuned simulation (``God's simulation''), but always a simulation.
Our `deeper level of understanding' of the symmetries of the
system (in both the obvious and abstract senses), has allowed us to perform
a creative analysis and deduce the future state whilst, we hope,
circumventing most of the previous-required computation. Let
be the
amount of computation required to arrive at the result by this method.
I shall shortly address the issue of defining these `amounts of computation' more precisely, but for the moment let us assume this can be done in a useful manner. Then the above definition states:
For simple systems, obviously (think of statistical
physics), but for many classes of system, as we increase their size and
rule complexity, there will be a phase change where the curves
and
cross
. The crux is
that there is no discontinuity separating non-emergent from
emergent systems. There is just a phase change in the optimal means of
system prediction. Beyond this, perfect understanding of the
system does no better than a simulation. All useful predictive knowledge
is contained in the accumulation of interactions.
Before proceeding further, let us return to the issue of defining
and
. I aim this analysis primarily towards discrete, deterministic
systems, although many of the ideas could clearly be made more widely
applicable. The obvious problem is that the time required to complete a
given computation is machine-dependent. For finite computations the time
required by different Turing machines is just related by an arbitrary
polynomial. If this phase transition is a real phenomenon, it shouldn't be
machine-dependent. To remove this dependence, we must take into account
the complexity of the Turing machine calculating the predictions. I
therefore propose the following definition:
The complexity of a step is measured in terms of the Kolmogorov complexity of a representation of the computation - i.e. the minimal description length.
To justify the machine-independence of this definition, consider a general
cellular automaton (which clearly falls within our definition of a complex
system), with possible states for each cell, and a dependence
neighbourhood of
cells.
Given adjacent initial cell-states, we can determine the state
of a single cell at the bottom of a light-cone after
time-steps in
just
rule applications. The CA
is a mapping from a set of size
to one of size
. As this mapping
may be completely arbitrary, we can represent each step with some
bits. So, to leading order,
.
I shall now argue that is invariant under the following
transformations.
Clearly ,
. Thus
is reduced by a factor
, which is second order, and only
significant in the limit of large memory (
) and small
.
is obviously unchanged except for a small increase due
to the overhead involved in splitting up the problem.
Assume we compress cells into 1, which will now have
possible states.
, and
is unchanged.
I shall not attempt to consider a general transformation, but rather appeal to the intuitive idea that increases in Kolmogorov complexity will offset any decrease in computational steps. I postulate that this is true for complex systems in general, not just CA.
Having identified a fundamental interactive unit, and the complexity of the
interaction rules for any given system; we can define all computational
amounts in the above manner. Let us consider an idealised means of
prediction in that complex system, requiring an amount of computation
, based on perfect understanding.
Where is only really useful if
and
are not exponential in
, but have leading order
and
respectively, in which case
to leading
order. It is a positive measure of the range of possible levels of
predictive understanding we may have in the system (
we should simulate;
increasingly rapid
predictions). A related measure of understanding, which can be useful if
we wish to compare how different methods of prediction,
, fare as we
move around the space of relatively simple systems, is given by:
Note that, at the phase change, can have a
discontinuous gradient. Also, beyond this,
, and since
, we have that
. So in an emergent
system, our understanding can be at best zero. Our astonishment at the
fact that we cannot seem to predict emergent properties, stems not from any
failure to understand, but from an inherent property of the system,
brought about by the accumulation of interactions. A
small reassurance at least.
Now we need no longer deal with any explicit dichotomy between emergent and non-emergent phenomena. The perceived lack of understanding in the former is really just another way of describing the complexity of the map between initial state and final phenomenon. In the sense that a lack of knowledge of the initial conditions will usually cause increasingly poor predictions; this is analogous to a discrete version of chaos.
This explains the apparent paradox of the rules giving a succinct, complete description of the system, whilst still revealing almost nothing about it. Of course any single phenomenon may fall anywhere in the spectrum between trivial prediction and interesting emergence.
Does this necessarily reduce our attempts to understand emergent systems to `stamp-collecting'? (In the sense that all we may do is catalogue the results of simulations). Section 4 discusses this issue, demonstrating that there are profitable, interesting possibilities for the study of complex systems.