In this lecture we will explain what Algorithmic Information Dynamics is.
First of all, when defining a complexity measure, why would we need a measure of complexity
at all?
Suppose you are interested in diseases investigated by gene behaviour, and we identify a set of
genes that are more complex than healthy genes, why would that information would help us in
any way?
A complexity measure should only be advanced if one can learn something from its application
and tells you something about nature or behaviour of the system.
So what is Algorithmic Information Dynamics?
It is a new field that can be considered part or an alternative to the challenge of inductive
inference to which other very interesting approaches have also contributed, in particular
the fields of computational mechanics as introduced by James Crutchfield, general artificial intelligence
as defined by Marcus Hutter and of course algorithmic probability as defined by Solomonoff,
Chaitin and Levin.
The main advantage of our methods based on algorithmic probability is that they do not
constraint the computational power of the models that can be abstracted to explain a
piece of data, so instead of using Markov chain models or finite automata that are of
lower computational power than Turing complete automata and may miss some aspects of algorithmic
content, our proposal is not artificially bounded in any way and tries to take advantage
of the unrestricted nature of the models that can be produced and considered, that is the
full power of context-free grammars and Turing-complete computer languages.
A disadvantage, of course, is that the space is even larger
and its exhaustive exploration ultimately impossible due to uncomputability results,
but we have shown that numerical approximations can give us an edge in the challenge of causation
and thus it is worth it to try and push these boundaries.
To illustrate the core ideas behind the theory and see how Algorithmic Information
Dynamics can be applied, let me use a very popular discrete dynamical system, a 2-dimensional
cellular automaton better known as the Game of Life because of its similarities to some
basic but essential properties of life such as life, death, reproduction, mobility and
interaction.
You can see how starting with some random initial configuration, persistent patterns
emerge.
And in the density diagram one can see that some patterns are more resilient than others.
Another way to visualise the Game of Life is with a space-time diagram, so because this
is a 2-dimensional cellular automaton, adding time would create a 3-dimensional object showing
the evolution of the cells over time.
Now, as observers we may always have a slice of the space and time but rarely full access
to the generating rule that in this case is shown on top.
So as an observer we may always have a partial view at a given time.
This is important to realise because we will ask about the algorithmic complexity of the
evolution of certain patterns even though the algorithmic complexity of the entire system
is always the same disregarding time and space and thus the generating rule is always the
same.
So, as we had seen before, the algorithmic complexity of a deterministic dynamical system
at any time is always the same except for the term accounting for the runtime t which
is in the order of the logarithm of t.
But we can still ask about the algorithmic complexity of a small observation window in
a slice and snapshot of the space-time of the cellular automaton because there may be
mechanisms that can explain in shorter terms a single pattern as compared to the whole
system.
Additionally, while there is nothing random in a deterministic system, when interactions
happen outside the observation window but affecting inside the window, those interactions
may appear random not only to us but to any tool trying to characterise its behaviour
isolated from the rest of the system.
The Game of Life is some sort of ecosystem in which patterns emerge from the interaction
of particles that appear and evolve according to the rules of the this cellular automaton.
Here, for example, we have the most popular pattern in the Game of Life called a glider,
a glider is a set of cells that seem to move together in an orderly fashion and can be
considered to be a single entity because it is its continuous interaction that makes them
persist over time and space.
A glider only occupies 9 cells in a square matrix of 3 by 3 and so we can always zoom
in close enough to follow the evolution of a glider.
One can see, from the bottom of the figure that the glider moves but in doing so it actually
remains in only 4 different configurations in what would be a cycle attractor if no other
particle interacts.
The cycle has period 5 because once the pattern repeats itself then produces the same sequence
of behaviour every 5 steps.
So we can apply BDM, the order parameter in this plot, to study the change in complexity
of this pattern evolving over time, and we can see that actually the complexity cycle
is shorter than its configuration cycle, a period 2 versus a period 5.
So to this very simple idea is to what we call Algorithmic Information Dynamics, in
this case illustrated with a very simple case that already tells us something interesting,
that the complexity of the glider comes in 2 types only because, now is clear, every
2 steps the glider is actually a rotation of the configuration of its 2 previous steps.
One can perform this same analysis to other patterns that coexist in the ecosystem of
the Game of Life where global rules dictating the behaviour of the system are out of reach
but BDM would help us to analyse an observation window around a region with an evolving persistent
pattern.
And then all sorts of interesting patterns can be traced in detail and better understood
by characterising their change in complexity over time.
Here, for example, we have cases in which symmetry, preservation and decay characterise
the various emergent patterns of size up to 4 by 4 in the Game of Life.
This is how all small particles in the Game of Life can be traced in detail, some of them
die out after a short period of time but some others may continue indefinitely evolving.
In fact, the Game of Life ahs been proven to be Turing-universal which means it can
get into infinite computations and can produce any number of different and open-ended forms
hence increasing or decreasing the local algorithmic complexity of different regions of the automaton.
Here from left to right we have 12 small patterns up to 4 by 4 matrices that evolve.
So what about the characterisation of events.
Events also happen in the Game of Life, and they are actually the responsible for the
emergence of new particles in the cellular automaton, so they are fundamental for the
system to remain alive, so to speak.
Here are different types of collisions of the famous glider, one can produce artificial
collisions, place the particles in specific places to wait for them to collide knowing
how they’ll move.
There are 4 type of these collisions involving up to 4 gliders.
In a 4-particle collision new particles are created both temporarily and then permanently,
although the resulting particles are static even if stable or persistent.
I call this particle interaction a ‘near miss’ because the particles seem not to
touch each other even when they do interact and lead to a small increase in algorithmic
complexity before settling into a configuration of lower complexity than the original particles,
all consistent with what we see in the evolution, as particles colliding momentarily generate
new information that the cells in the observation window can explain only to a few steps later
converge to a low complexity static configuration.
Not all collisions are the same.
One can have the same 4 particles but arranged in a slightly different square matrix leading
to a longer transition of new particles and a different cycle attractor with period 2,
as this last configuration or fixed point cycles between 2 configurations can show.
2-particle collisions in diagonal lead to annihilation, and this can be traced by BDM
in detail.
And some collisions even lead to open-ended emergence of particles of never ending dynamics.
At the end, the algorithmic dynamics of all cases can be aggregated and a clear pattern
emerges, there are basically 3 type of collisions among particles of up to 4 gliders.
Some produce more diversity of other particles and others simply decay.
In both the density plots showing the attractors and basins of attraction, and also the plots
of the algorithmic dynamics this can be witnessed.
We will see how we can come from tracking particles and characterising events to reconstructing
the dynamics of them by using Algorithmic Information Dynamics.