So we saw in the last lectures how we can quantify algorithmic randomness by using computer
programs running on some reference universal Turing machine.
But one could think that it is always possible to find some language in which a particular
object had a short encoding, no matter how random.
For example, Alice and Bob could agree to compress all the content of the Encyclopaedia
Britannica in a few symbols, so when Alice presents Bob with those symbols, Bob would
know Alice meant the Encyclopaedia Britannica.
Algorithmic Information Theory (AIT) would mean little if the complexity of something
could be determined so arbitrarily by renaming things with any number of symbols.
AIT requires the program to reconstruct the original object from scratch so there is no
coding cheating.
Bob would need a computer program to reconstruct the Encyclopaedia Britannica without any external
help from Alice or anyone else.
It would also look like one would need to specify the specific programming language
and the particular universal Turing machine on which those computer programs would run
for algorithmic complexity to work or make sense.
Otherwise, one would be able "rename" things and make anything look random or simple by
changing the underlying language and Turing machine.
So let's consider the following sequence that has 3 symbols, 0, 1, and 2:
We can show that this sequence can be generated by a small computer program like this one:
whose length is no more than 56 bytes no matter how long the sequence to produce the same
pattern.
However that is in the Wolfram Language running on Mathematica.
What if instead we had used Lisp, Java or Visual basic?
It seems that the result would then depend on the computer language chosen.
And even in a single computer language there may be different computer programs of different
size can produce the same object.
For example, the following two computer programs can generate any number of digits of the Thue-Morse
sequence and both are different in length even though both are small and generate the
same sequence.
So how to deal with different computer programs in possibly different computer languages with
different lengths?
Fortunately, the Invariance Theorem as proven by Kolmogorov, Solomonoff and Chaitin, tells
us that the difference between any two computer programs producing the same object is at most
a constant from each other.
More formally, the so-called invariance theorem establishes that the difference of the lengths
of the minimal programs on any two computer languages L1 and L2 is always bounded by a
constant that depends on L1 and L2 but not of s:
The way to see this is by thinking in a translator program between two languages L1 and L2.
Because what the invariance theorem says is that one can always write a 3rd computer program
of fixed length capable of translating between any two languages L1 and L2.
This is actually very clear with the computer language Java because one of the innovations
of Java when it was introduced was that there was a Java Virtual Machine or JVM that made
Java multiplatform in the sense that you could run your Java program on any platform without
changing any language code.
That is because the many JVMs were acting as a translator, or officially called a compiler,
between the Java programming language and each machine code for different platforms
such as Unix and Windows.
So if the translator is shown in blue, one has to only add the translator to every computer
program written in some language to convert it into another program in another language,
both languages producing the same sequence of interest.
The length of the compiler or the length of the blue part is the same for all input strings
and so it is constant.
So if L1 is the Wolfram Language and L2 is Java, then the invariance theorem tells that
finding the shortest computer programs to measure the algorithmic complexity of a string
is about the same length up to a constant.
In another more practical example, what the "c" in the invariance theorem characterises
in a biological context, for example, is that the DNA and a set of reading and writing chemical
machines called ribosomes form a couple of language and compiler able to transcribe and
translate DNA into proteins effectively from one language into another.
So ribosomes can be thought as some sort of compilers between the DNA, RNA and the protein
space with the ribosomes always of same complexity independent of what they are reading or writing.
can be reproduced with a code no longer than 56 bytes no matter how long the sequence with
this pattern is required.
Well, that is not entirely true.
Actually the code has to grow by a little bit if we want to produce longer sequences
with the same pattern.
It does grow a little bit because one has to determine the end of the algorithm, that
is when do we wish the sequence to come to an end.
And that number does make the code to grow a bit.
In fact, classical information theory tells us that we can encode an integer n in about
logarithm of n bits, because remember we can always guess a number in about logarithm of
n yes and no answers.
You can see how running this code with very large numbers, the byte count does actually
change for very large numbers:
So despite how trivial this extremely little piece of information may look and how kind
of little difference it makes, it is not only mathematically precise but it will turn out
to be the most important little piece of information in the field of Algorithmic Information Dynamics,
and you will see soon why.
Not to keep you waiting but not getting into details, the main idea is that, unlike a deterministic
system that has a well-defined generating mechanism such as this sequence and its generating
formula, other systems that may be subject to some source of randomness or are interacting
with other systems, this logarithmic change will not be longer be respected and the more
removed from the logarithmic term the more it will tell you some unvaluable about the
system's behaviour and its underlying causes.
To understand this better, in the next unit we will cover the theory of dynamical systems
for you to understand what a dynamical system is before we finally get into the subject
of Algorithmic Information Dynamics.