A theory can be very useful
because it introduces the necessary objectivity
but keeps some necessary subjectivity for my purposes.
This here is the theory of algorithmic information,
also known as "Kolmogorov complexity."
Basically, Kolmogorov complexity of a string is the length in bits
of the smallest computer program that produces the string.
So, if someone asks you
which of these strings on your screen look more or less random,
with traditional probability theory, you wouldn't be justified in saying
that the string at letter "b" is the least random -
because any of the three strings would have exactly the same probability
being produced by a uniformly random process,
generating the strings at the same length.
But, with Kolmogorov complexity, you can find a short program
that produces the non-random-looking string
to justify its non-random character.
For example, this program produces the string of alternating zeros and ones,
and... it can produce a string arbitrarily long, with the same pattern -
without having to increase the program size itself.
This means that this string of alternating zeros and ones
is of low random complexity.
In other words, this program is the compressed version
of an arbitrarily long string containing this alternating pattern.
Before coming back to Kolmogorov complexity,
let me introduce Wolfram's behavioral classes.
Stephen Wolfram found that cellular automata and other systems
can be basically classified into four behavioral classes.
Class I, for example,
are systems that evolve into homogeneous states or simple behavior.
Class II develop into periodic states, such as fractals and crystal-like objects.
Class III systems are random-looking ones.
Class IV display persistent structures over time,
with parts looking random and other parts looking simple.
Here are some examples of cellular automata
that display different complexity.
You can see the evolution of cellular automata for some number of steps,
and their compressed and uncompressed lengths plotted
next to the cellular automaton evolution.
You can see that the evolution of Class III cellular automata,
like Rule 30 that you can see on your screen, looks very much random.
It's very hard to compress - while simple rules are very easy to compress.
However, notice that if something is hard to compress with an algorithm,
it doesn't mean that it cannot be compressed.
This is why the compressibility approach - based on Kolmogorov complexity -
retains some subjectivity that I find useful to classify systems.
The subjectivity of Kolmogorov complexity actually comes from the fact
that the measure is... [uses] a fancy name - semicomputable.
That means that no Turing machine can compute the length
of the shortest program for a given string in general.
So, only approximations or upper bounds, to be more precise, are possible.
But, this is a desirable property of a measure of complexity,
because it is because of its power that it turns [out] to be semicomputable,
and it is this thing that we call "semicomputability" -
that compression is a sufficient test for nonrandomness.
That means if something is compressible then for sure it has low complexity,
but not the other way around.
And this slide shows that by looking at the compressed lengths of evolution
one can classify the behavior of these cellular automata.
This is very similar, from my perspective,
to another important contribution of Alan Turing to science -
that is, Turing's imitation game, also known as the "Turing test."
In the original Turing test, the test consists in determining
whether behind the screen there is a human
or a computer answering a question.
Turing used this approach to give an answer to the question
of whether computers could be intelligent -
the question that actually gave birth to the field of artificial intelligence.
Turing replaced the question with a test
and claimed that if a computer should take the Turing test - that is,
that it would fool a human to make it believe
that at the other end there is a human instead of a computer -
then the computer should be declared intelligent.
In my approach to computation,
the compression algorithm can be seen as an interrogator
of the programming capabilities of a system -
where the questions are initial conditions to the programs
and the answers are lengths of the compressed...
answers to these external stimuli.
If the source is somehow programmable, then one should be able to declare
that source to compute and to be some sort of computer.
But, unlike in Turing's test,
where things are black or white or intelligent or not,
I would like a graded measure of computation -
a measure indicating whether I can actually program something
to behave like a computer program.
So, I can come up with a measure based on this compressibility
that can be consulted in any of my papers on this subject,
if you go to my webpage.
So, this approach can deal with situations like Chalmers' rock,
where I can assign a very low computing degree
indicating in agreement with our intuition
that a rock is not like a computer, because it is very difficult,
if not impossible, to program anything on a rock -
to carry out any computation, if that makes any sense actually
to think of programming a rock.
And, since computers such as the "Game of Life"
or this Wolfram "Rule 110" that you are looking at on your screen
that have proven to be Turing universal
have large programmability scores in agreement [with] the knowledge
that we have about this cellular automaton -
unlike this other one that is another cell automaton
that behaves very simply and actually is very difficult to reprogram,
or to do any computation on it other than very simple things.
And, the measure can be applied to other [entities] than computers
by measuring this programmability index of physical and biological systems.
Here is a sketch of how this would work,
sorting various systems by variability and controllability,
which are the two orthogonal properties
that I think are fundamental for computing.
For example, for weather and Brownian motion
that have great variability, they are very hard to control.
And, on the other extreme, rocks that have a lower variability
and are therefore trivially controllable are not in the programmability diagonal.
So, in the diagonal view you see living organisms
and another programmable systems.
And, in this way I think the question of life
and how to recognize natural and artificial intelligence,
and also natural and artificial life, is deeply connected to the question
of how to recognize computation -
and whether things can be reprogrammed or not.
After all this, you may ask what am I doing in one of the best
medical universities - on Karolinska Institutet?
Well, one can use... because I'm a computer scientist, by the way.
Well, one can use and exploit all these ideas
to reprogram living systems, to make them do things at will.
In the end, this is the whole idea of programming something.
Here is an example of finding the right input for phorphyrin molecules
to make them behave in different ways.
That is what it means to program something:
to find the inputs for the desired output.
It is all about mapping the parameter space to the output space.
In this case, we call it
the "conformational space" of these molecules.
The conformational space is just a space of possible shapes
that these molecules can form - and that is interesting
because in biology, shape is function.
This is a very powerful idea because one can program molecules
to do things like carrying out a payload to be released
when some conditions are met - releasing, for example,
a chemical that may be used for biological markers
or even to fight diseases.
As a proof of concept, we have applied these programmability measures
to a large set of biological simulations from a world-known database
of biological models called "BioModels."
We have found that the programmability measures
are sensitive to the robustness of different models,
apparently distinguishing between models
that are related to cellular versus metabolic processes.
Here are some plots of the programmability trajectories
of different models, some showing low variability
while others have high variability but different degrees of controllability.
[ end of audio ]