So in this lecture we will see how we can
take advantage of the power of our causal

interventionist calculus based on algorithmic
information dynamics not only to describe

and study objects and find out causes but
steer and manipulate systems.

Because we are using computable models and
algorithmic techniques, we call this type

of manipulation ‘reprogramming a system’.

One of the greatest challenges in science
is that we are always in disadvantage as observers,

we can only have a partial view at a single
scale and away from isolation.

For this reason we always have to deal with
what we call noise and with partial representations.

Representations come in all flavours in science,
we often like to model phenomena with systems

such as differential equations but sometimes
also as networks and discrete systems.

In fact, for almost any representation one
can come up with a set of equivalent representations

fully describing the same systems but allowing
us to see different features of the same phenomena.

We have seen how using some measures looking
at different features and representation would

bias our results, and we have also seen how
to attempt to move away from language dependent

measures towards more objectives means to
analyse data to infer models.

We have analysed several dynamical systems
and we have seen how to characterise networks,

it is now time to move a step forward and
see in what ways finding out possible causes

for observations can help us steer and manipulate
those same systems.

By showing this we definitely leave behind
more descriptive methods such as traditional

statistics that not being able to find models
by themselves leave us with little chances

to find handles to manipulate systems.

However, once knowing the causes, and what
produces what, we can start manipulating models

and systems to behave in different ways, in
particular in ways that we may find useful

for our purposes.

So in this unit we introduce the concept of
reprogrammability from an abstract and mostly

theoretical point of view but in the next
unit you will see how this can be applied

to real-world systems, in particular biological
cells, for different purposes.

So here we have some of our most recent results
in this area.

We show how to reprogram a cellular automaton
to emulate any other cellular automaton.

The way we did this was by way of what is
called a compiler in computer science.

A compiler is a small computer program that
does nothing but translate between 2 different

languages or systems.

Is a real-time interpreter that allows you
to transfer data from one system to another

on such a way that both systems can communicate
between each other.

So what we did was to take a random cellular
automaton and we would find a compiler based

on exhaustive exploration and hacking tricks
in order to find the right initial condition

for the cellular automaton to simulate some
other cellular automaton.

By performing this exhaustively we were able
to break some boundaries imposed by Wolfram’s

classes.

You may remember from previous lectures that
Wolfram’s classes divide systems, in particular

Elementary Cellular Automata into 4 classes
of different qualitative behaviour, so classes

1 and 2, for example, are classes of systems
that display very simple behaviour.

Then class 4 are systems that produce random-looking
behaviour and class 3 systems display structure,

a combination of simple features and random-looking.

However, what we were able to show, is that
we were able to reprogram instances in every

one of the Wolfram classes and make them behave
as cellular automata from all other Wolfram

classes.

Here we have an example of a cellular automaton
emulating other by using a compiler.

The compiler is only used once on every computation,
at the beginning mediating between an initial

condition and the normal computation of the
emulating cellular automaton.

Then the compiler transforms that initial
condition into the instructions for the emulating

cellular automaton to emulate another one.

On the right you have emulating and emulated
cellular automata examples illustrating how

we were able to reprogram cellular automata
to behave as any other providing evidence

that computer programs are incredibly reprogrammable.

With all this information, we were able to
reconstruct emulating networks, two cellular

automata would be connected by directed edge
if one cellular automata was able to emulate

the other.

We found many interesting properties in such
evolution networks, including ways in which

we were able to find long chains of emulations
and also rule hubs that were more reprogrammable

than others or more prone to be emulated by
others in some way reestablishing the Wolfram

classes but more in a pragmatic way rather
than fundamental.

More striking is the number of cellular automata
able to emulate other cellular automata of

very different qualitative computational behaviour.

What we found is that, the more cellular automata
we explored the more reprogrammable they were

in terms of how many other cellular automata
of their own size in number of colours they

were able to simulate in comparison to those
that were not reprogrammable at all.

This kind of reprogrammability is actually
a stronger version of Turing universality

and is called intrinsic Turing universality,
so finding that more and more computer programs

are reprogrammable in this way we also found
that our results seem to suggest that Turing-universality

is pervasive.

So equipped with all these tools we were actually
able to find several new universal cellular

automata, some of them quite interesting.

These examples illustrate 2 cellular automata
that are the result of combining several Elementary

Cellular Automata.

In these figures each of these cellular automata
are running a rule 110 computation and we

have shown that they are able to emulate rule
110 therefore are Turing-universal themselves

because rule 110 is Turing universal.

These are actually possibly the only new universality
results involving Elementary Cellular Automata

that have been found in the almost last 2
decades.

Remember that Turing universality means that
a system can carry out any computable function

and that means that, for example, these extremely
simple cellular automata can emulate things

like your entire Microsoft Windows computer,
even if certainly very slow because they have

very little resources at any given time so
they would need to do all sort of tricks to

re-encode the computation but yet they would
be able to do so.

So one fundamental question to answer in connection
to algorithmic dynamics, is how inducing perturbations

to a system in terms of their contribution
to their underlying models, would actually

change the dynamics of that system.

Performing perturbations at the level of the
system to change the possible generating model

is equivalent to simulating a change in the
original model which can then run for longer

to compare its output with the original system
output and see the differences.

So we did a first simple experiment, we took
all possible random Boolean networks with

up to 5 nodes which as you known are many
because their number grows super exponentially

yet because they are small we could explore
all them and extract some statistical significant

results.

So we calculated which perturbations would
be positive, negative and neutral as defined

in the previous lessons, that is which perturbations
would have an effect to the original system

model that would force it to incorporate new
elements to account for the new changes at

the system’s level.

And what we found was also something that
we were expecting and can turn out to be of

extreme help, that moving systems on the algorithmic
complexity landscape has a predictive effect

on the dynamical landscape of the system,
that is in the phase space of a dynamical

system.

So from the random Boolean networks experiments
we were able to produce the results on figure

d.

The small difference between cases small but
significant because the number of attractors

in such small graphs is tightly bounded but
given the number of cases and the average

difference the results are consistent with
what we also found on larger networks.

In figure (e, f and g), for example, numerical
calculations of the change in number of attractors

in simple directed complete graphs, ER and
scale-free Boolean networks shown very consistent

results.

In a complete graph there are only a few possible
attractors because everything is connected

and it only depends on the direction of the
edges and the node functions, but only negative

perturbations produced more attractors, positive
and neutral perturbations preserved the number,

as we had expected.

In the results for 20 aggregated results from
Erdos-Renyi random networks the separation

was even more clear and consistent with the
exhaustive experiment with small Boolean networks.

Negative perturbations, that is those that
move the network to greater algorithmic randomness

increase the number of attractors, while positive
reduce them and neutral preserve them.

Scale-free networks, like regular networks,
were found to be more resilient to perturbations

but again only negative perturbations were
able to increase the number of attractors.

Notice that there are very few alternatives
to doing something like this to control and

manipulate the dynamics of networks.

There is an area of active research on network
controllability but all of them involve assuming

distributions, having access to the precise
node functions which most of the time we don’t

such as in the case of neurons and genes,
and they also tend to assume that all systems

are linear or near equilibrium which they
likely are not in the real world, but none

are necessary in this approach connecting
the algorithmic information space and the

dynamical phase space.

From these first principles, where systems
which are far from random, displaying an inherent

regular structure, have relatively deeper
attractors and are thus more robust in the

face of random perturbations, we can derived
a (re)programmability index according to which

algorithmic causal perturbations of network
elements pushing the system towards or away

from algorithmic randomness reveal qualitative
changes in the attractor landscape even in

the absence of a dynamical model of the system.

For example, depending on the original complexity
of a network, negative perturbations will

increase the number of attractors and also
make them more shallow, significantly changing

the dynamics of the system.

A network is thus more (re)programmable if
its elements can freely move the network towards

and away from randomness thereby also changing
its dynamics.

Also notice the asymmetry of the programmability
curve, because for random edge perturbation,

simple networks are more sensitive than random
networks, and this is some sort of thermodynamic-like

phenomenon connecting computing back to statistical
mechanics in a very interesting way.

This reprogrammability index assigns low values
to simple and random systems and high values

only to systems with non-trivial structures,
and thus constitute what are known as a measure

of sophistication that tells apart random
and simple cases from highly structured, in

this case quantifying the algorithmic plasticity
and resilience of a system in the face of

perturbations.

This plot shows what we call the (re)programmability
space defined by the Cartesian product of

two programmability measures.

One is relative (re)programmability Pr(G)
that takes into account the sign of the different

segments of the information signature of G
that gives us the number of elements that

can send a network towards or away from randomness
and how much of those elements in the form

of its information signature are below or
above zero.

The other measure, absolute (re)programmability
PA(G) accounts for the shape of the signature

σ(G).

Both of these indices contribute to the information
about the (re)programmability capabilities

of a system such as a network.

The combined version is, effectively, a weighted
index between the two (re)programmability

measures that maximizes certainty measured
by the magnitude of the vectors, where the

closer to (1,1) or (re)programmability vector
of magnitude √2, the greater the certainty

of G being (re)programmable.

So in the next unit we will see how we can
apply all these ideas from this unit to applications

in behavioural, evolutionary and molecular
biology, in particular to cognition and genetics.