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.