Coming back to the formal definition of algorithmic probability, denoted by m
it can be seen that the largest term in the sum of the equation is obtained when the denominator
is the smallest, that is, when the length of p is the smallest, namely the shortest
length of program p in bits that produces s, but the length of the shortest program
is nothing else but the algorithmic complexity of s.
Hence we have found a beautiful connection between frequency of production of a string
and its algorithmic complexity.
The algorithmic Coding theorem formally establishes the connection between algorithmic complexity,
here denoted by K, and algorithmic probability.
The theorem establishes that the algorithmic complexity of a string is proportional to
the negative logarithm of its algorithmic probability.
In other words, if a string is produced by many programs then there is also a short computer
program that produces the string and if a short computer program produces a string then
it will also be more likely to be produced by more computer programs.
This actually suggests a way to calculate algorithmic complexity by way of algorithmic
probability avoiding the use of lossless compression algorithms so widely used to approximate algorithmic
complexity.
We will see later how such a method can be implemented when introducing Algorithmic Information
Dynamics.
The implications in the real-world of something like algorithmic probability are very broad
and fascinating if one allows some speculation.
For example, according to classical mechanics the world may be an unfolding algorithmic
process.
Suppose that all phenomena in nature can be carried out by a Turing machine as a computation
and therefore sub-processes are also shorter computations.
Then the algorithmic probability m of a physical event s would tell something about s actually
happening.
In fact, algorithmic probability can be used to explain the generation of structure out
of randomness generating order in the universe out of nothing.
We have a few papers on the subject and one essay that was awarded a prize by the Foundational
Questions Institute and you can find it in the references section.