In this lecture, we will see how we can
apply algorithmic information dynamics

to integer sequences 
and behavioural sequences,

and we will introduce you 
to what we call 'algorithmic cognition'.

So, if we want to work 
with integer sequences,

one obvious experiment is to see 
whether we can correctly characterise

the hundreds of thousands of sequences 
in a very popular database,

called the 'On-line Encyclopedia 
of Integer Sequences',

populated by people and based on 
some recursive algorithms

that generate the sequences.

Many more experiments can be done, 
and we have many open projects that

you can undertake to apply algorithmic
information dynamics to these sequences.

But here we did a couple 
of very interesting experiments,

with very positive results.

I have myself introduced 
a few entries in the database.

I contributed with about seven sequences
that were not already in the database,

based on different algorithmic processes.

One of them is precisely the progression
of number of Turing machines

used for the CTM method, for example.

With so many sequences in the database,
it is today [somewhat] difficult

to produce new ones interesting enough 
to have them introduced.

But many numbers of these sequences 
make it to the database,

and it is a great dataset 
for testing purposes.

So, in the database 
is not only the sequence,

but also the code in one 
or more computer languages

and the description of those sequences.

What we found was very interesting:

that the textual description length, 
as derived from the database

or extracted from the database, 
is - as illustrated on the left -

best correlated with BDM 
than [with] any other measure,

such as Shannon entropy 
or lossless compression.

And, we also found 
that we were able to show -

see this on the right -

that BDM performed best when comparing
the length of the program,

also extracted from the database 
that generates each sequence,

and the BDM values 
of the integer sequences

also better than the other two measures.

And this is exactly 
what we were expecting,

because it means that our estimations 
of algorithmic complexity -

by way of algorithmic probability, 
estimated by BDM -

are truly capturing something else 
that other measures cannot.

And what they are capturing 
is exactly in the right direction,

because it is correlated 
with the description length

of the algorithm 
generated in the sequence,

or the length...in bits of the algorithm
precisely producing those sequences.

So, one great source 
to understand those experiments is,

of course, the original articles.

But we can move now to another type 
of real-world sequences -

what are known as 'behavioural sequences'.

And, in particular,
experiments that we conducted

with sequences 
coming from different sources,

sorted from cognitive-simple to more 
cognitive-sophisticated organisms.

So, first is a landmark experiment -
even if sometimes controversial,

conducted with so-called redwood...
and blood ants -

conducted by Russian researchers 
several decades ago

and then redone 
almost every decade again.

The idea was to place food 
in the leaves of a binary tree

that serves as a maze 
for forager ants to find that food.

Once they find the food,
they come back

to communicate the location of the food
to other ants in the colony.

All aspects of the experiment 
were controlled,

for example, to avoid pheromone 
traces in the way.

And we won't spend time
explaining the details

because you can go to 
the original sources -

you can go directly 
to both their papers and also ours.

So, the hypothesis to test was:

whether the forager ants would take
longer to communicate information

about the location of the food,
when the food was placed in locations

that require a more
complicated number of turns,

in contrast to having placed 
the food in, for example,

the leftmost branch in all cases.

So, at every bifurcation, 
the ant can choose left or right,

that can be encoded in binary by,
for example, a letter such as L or R,

standing for left and right.

Then, an easiest path to the food 
could be L-L-L-L

in this example on the screen,
which means:

'take always the left branch 
and you will find the food'.

And that is a very short description.

In contrast, something like L-R-L-L 
is slightly more complicated,

but perhaps not as much [as] L-R-L-R.

So, if the hypothesis is right, 
then one could say

that ants are somehow able to compress
some of the instructions

to transmit them to other ants,
because they find that

there are some simple ways to describe
something that is intrinsically simple.

So, the researchers measured the times 
that ants would take

to accomplish this communication task,

and they noticed that, indeed, 
there was a correlation

between string simplicity 
and communication time.

But they were unable 
to precisely quantify this.

And, it was not until we applied 
our methods

that can deal with short sequences, 
and both sensitive and specific enough,

that the suspicion could be quantified.

Here we can see that by using CTM -
BDM is here not necessary

because the string length 
is less than 13...

So we can use directly CTM only.

The only measures able to quantify and
confirm the original paper hypothesis

[are] both the approximations 
of algorithmic complexity

and of logical depth using CTM.

This is another more recent experiment

with perhaps one of the insects 
with most simple behaviour - a fruit fly.

This experiment 
is much more sophisticated,

and to understand it in detail, 
you must again read the original paper.

But let me try to explain briefly 
how we were able to test the CTM and BDM

on this dataset and experiment.

So, it has been long believed 
that flies are very simple -

almost like robots - in that they only 
react automatically to external stimuli

without engaging 
in [many] cognitive processes.

So, the experiment consisted in placing
a fruit fly inside a cylinder.

The fly is attached to a torque 
that detects the fly's turning direction -

with the fly actually not moving at all,

because it is connected to
a brain signal detector

through diodes in its head.

So, the cylinder emulates 
three situations,

one in which there are no patterns at all 
when the fly turns,

no matter what the fly does;

one in which there is a vertical stripe

giving the fly some feedback 
about its turning behaviour;

and finally, one in which the pattern 
inside is uniform with some texture.

So, in the last two cases,

there is external information
coming to the fly's brain.

But, in the so-called 
'open loop' environment,

there are no cues or external information 
given to the fly.

So, the experiment is designed to measure 
if the fly actually performs any strategy,

or engages in some cognitive process - 
even in the absence of any input.

That would debunk the idea
that flies have no internal experience

and are just blind sensors 
that react to external input.

Without having to repeat the experiment,
but applying BDM

to the behavioural sequences 
that were extracted from that paper,

there is a sequence of left-right turns
of the fly's intention to change direction

that were recorded for the experiment.

We were able to confirm 
that flies do not fly randomly

in the absence of information,
but implement a strategy

of heading towards 
a single direction first -

probably hoping to find some feature
indicating their whereabouts.

But they also performed
the computational work

according to our approximations of
logical depth,

because despite the simplicity 
of their movements,

they were as sophisticated as those 
performed in the uniform case

and also in the one stripe experiment.

Whereas, in the original experiment, 
they had to actually see brain activity

by connecting diodes in their brains 
to determine how much cognitive activity

they were performing, in line with what
we saw with our measures.

In another experiment, 
[this time involving] rats -

an animal of apparently 
much greater intelligence than insects

such as flies or individual ants -

rats were presented
with a computer program

that would challenge them 
in their cognitive abilities,

to predict an outcome
consisting in a signal

that would be shown in one of two holes.

And, if they get it right,
they would be rewarded with sugary water.

It will show a sequence,

produced by an algorithm
of increased sophistication and length,

and there will be three of these
increasingly sophisticated algorithms

trying to fool [the] rats.

The first one was [a] very simple one -
the simplest among the three -

and it would be completely repetitive,

showing the signal in a cycle
of period two,

So it would show in one hole, 
and then the other and so on -

completely predictable.

And, after some attempts,
the rats would crack it

and get... 
100% of the rewards.

Clearly the rats were up to the task

of outsmarting a very simple algorithm,
like this one.

The hypothesis to test was to see 
what strategy the rats would take

when outsmarted by a more
sophisticated algorithm,

and whether they would still be engaged 
cognitively in some way,

or [would they] just give up and
behave randomly as a result of giving up.

Here again, our results were also in line

with the results 
from the original experiment,

and they showed that rats
faced with algorithms that outsmart them -

making them fail in predicting in
which hole the signal would appear -

rats embraced pseudo randomness,

meaning that they were purposely
trying to behave [randomly] as a strategy.

This may mean 
that trying to behave [randomly,]

as opposed to behaving [randomly,]
is actually some sort of strategy -

and a strategy probably taken by some
sophisticated animals,

such as rats when they are outsmarted 
by competition or a predator.

One can see in the figures...

how randomness increases 
from algorithm one to three,

even when the standard variation 
is as small for algorithm three

but the median of the rat behaviour 
is actually larger -

a perfect monotonic progression.

So, we can see in our results

how the sophistication of the algorithm 
from one to three increases

But, when outsmarted by algorithm three,

the logical depth
of the animal behaviour does not drop,

but remains as high 
as for algorithm two

that was already being 
a cognitive challenge for the rat -

as opposed to both the complexity 
of algorithm one and two.

Moreover, one can also see

how the behaviour matches the reward
in algorithm two and three,

indicating that the rat
was almost as successful

embracing a random strategy 
for algorithm three,

than when faced with algorithm two.

We were also able to pinpoint
the exact moment in time

when different rats were able 
to crack different algorithms -

with algorithm three, labelled as
'Competitor Three' in these figures,

remaining mostly unbreakable,

as the behaviour of the rat
never comes down

and remains as complex
as the algorithm itself,

producing pseudo-random behaviour.

For the other two 
more simple algorithms, however,

the rat eventually sees through 
and diverges from the algorithm behaviour.

To make sense of these plots,

take into consideration 
the scale of the y-axis

Finally, let's move to 
an example with humans.

And this time, it is us that performed 
the experiment from start to finish,

with the participation 
of about 3,500 people.

And that has its rewards,

because the world's media 
got very excited [about] our results

and made articles about them.

The experiment consisted [of] five tasks

asking people to produce randomness 
in different ways.

In the first task,

they were asked to produce
a sequence of heads and tails

as if they were tossing a fair coin.

Then they were asked to picture 
a random order of a pile of cards

and guess which one 
was on top of the pile.

They were also asked 
to produce a sequence

as if they were throwing a dice.

And finally, they were also asked 
to place dots at random

and create a grid
that would look random to them.

The results were very interesting.

We found that people at age 25

were able to produce 
the highest algorithmic randomness,

measured by CTM and BDM.

And this was consistent
across all five tasks,

and was independent of all sorts
of variables that were controlled -

because people were asked for their
gender, educational background and level,

language spoken and even paranormal
beliefs.

No other variable but age 
produced a difference,

meaning that, for example,

there is no difference in randomness 
production between men and women.

The results are in perfect alignment 
with many other studies,

suggesting that cognitive abilities peak 
at about age 25 before coming down.

But do not freak out!

The variation is minimal
and barely noticeable.

Here it looks large,

because that is the intention 
of the experiment and these plots.

But it does not mean 
that we will all become dumb

or were dumb when we were kids.

There are also ways 
to keep the mind sharp,

and some traits can be
exchangeable [with] others,

because one may be able 
to compensate disability

with more knowledge 
accumulated over time.

And actually, perhaps it is the
accumulation of that knowledge

that makes us produce 
lower randomness after 25.

But notice how interesting 
[this experiment was]

because it is, in some way, 
[a] sort of reversed Turing test,

where people - 
even if they didn't know it -

were kind of competing 
against computer programs

to see which ones were able to produce 
better algorithmic randomness.

So, people, without knowing,

were asked to behave 
as the longest computer programs

producing the highest 
algorithmic complexity sequences.

So, if these were again 
people [of] 25 years of age,

[they] would have better chances 
[of beating] a random computer program

and producing greater
algorithmic randomness.

So, in this unit, we saw how we can apply
algorithmic information dynamics

to behaviour and cognition 
of humans and animals.

And, many questions and
challenges remain open.

And, we have also written several other 
articles that may be of interest to you.

And even some independent groups
are now using our measures

in all sorts of areas of specialities,

in particular psychometrics to test 
the cognitive abilities of the human mind.

Here on the screen are some references
and you can see how fruitful it has been.

We call this line of research 
'algorithmic cognition'.

In the next unit,

we will see how 
CTM, BDM and algorithmic dynamics

can also contribute, 
to discover some interesting facts

about biological and artificial evolution.

[ end of audio ]