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

to integer sequences and 
behavioral 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 if,
whether we can correctly characterize

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 algorithm 
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 Turin machines used

for the CTM method, for example.

With some many sequences in the database,
it is today, somehow, 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 
to any other measure,

such as Shannon entropy or
lossless compression.

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

as it is on the right,

that BDM performed best
when comparing the length of the program

(also extracted from the database),
that generates each sequence,

and their 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 estimatons 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
generating the sequence,

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

So, one great source to
understand those experiments is,

of course, the original articles.

But we can move on now to other types 
of real world sequences,

what are known as "behavioral 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 or 
ant-wood and blood ants

conducted by Russian's researchers
several decades ago

and then redone,
almost every decade again.

Uh, 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 experiments 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 but,
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,

as 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.

Um, in contrast, something like L-R-L-L
is slightly more complicated

but perhaps not more than 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 simpler ways to describe 
something that is intrinsically simple.

So, the researches 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 
are both sensitive and specific enough,

that the suspicion could be quantified.

Here we can see that, by using CTM,
because BDM is here not neccessary,

because the string lenght 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 behavior, 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 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 of placing a
fruit fly inside a cylinder.

The fly is attached to a torque
that detects the fly turning direction,

(with the fly actually not moving at all),

because it is connected to
a brain signal detector

through diodes, uh, 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.

Uh, one in which there's a vertical stripe

giving the fly some feedback 
about its turning behavior

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 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 they are just blind sensors
that react to external input.

Without having to repeat the experiment 
but,

applying BDM to the behavioral 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
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 involving - 
this time - 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 of a signal

that would be shown in one of two holes,

and, if they would 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 would 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 um,
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.

And 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 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 behavior
is actually larger -

in 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 behavior
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 behavior 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, labeled as
"Competitor Three" in these figures,

remaining mostly unbreakable,

as the behavior of the rat
never comes down

and remains as complex as
the algorithm itself,

producing pseudo-random behavior.

For the other two 
more simple algorithms, however,

the rat eventually sees through, and 
diverges from the algorithm behavior.

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 it 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 paranomal beliefs).

And 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's the intention of 
the experiment and these plots.

But it does not mean that 
we will all become dumb

or were dumb when were were kids.

There are also ways to keep 
the mind sharp,

and some traits can be
exchangeable by others,

because one may be able 
to compensate disability

with more knowledge accumulated
over time.

And actually, [it is] perhaps
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,
some 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 can apply
algorithmic information dynamics

to behavior 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 specialties,

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 is 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 [in discovering] some 
interesting facts

about biological and artificial evolution.

[end of audio]