Question:
---------


Did Kolmogorov develop a set of axioms for probability theory motivated by Algorithmic Information Theory in the 1960s?


Context:
--------


In 1965, Andrey Kolmogorov considered three approaches to information theory(combinatorial, probabilistic, and algorithmic) [1] where in the algorithmic approach he introduces the Invariance theorem for the minimal description of datasets $X$ relative to Universal description languages $U$ and $U'$:


\begin{equation}
\lvert K\_U(X)-K\_{U'}(X) \rvert \leq \text{Cst} \tag{1}
\end{equation}


which allows us to formulate the Universal Distribution, an effective formalisation of Occam's razor [2].


In essence, he introduced the foundations for Algorithmic Information Theory and in the conclusion he clarifies that his motivation for doing so is to provide a clear definition of randomness as well as a robust foundation for probability theory where all probabilities have a deterministic and frequentist nature.


In fact, his PhD student Leonid Levin would rigorously define the algorithmic probability of observing a dataset $X$:


\begin{equation}
-\log\_2 P(X) = K\_U(X) - \mathcal{O}(1) \tag{2}
\end{equation}


which would later become known as Levin's Coding theorem [3].


References:
-----------


1. A. N. Kolmogorov Three approaches to the quantitative definition of information. Problems of Information and Transmission, 1(1):1--7, 1965
2. Peter Grünwald and Paul Vitanyí. Shannon Information and Kolmogorov Complexity. Arxiv. 2004.
3. L.A. Levin. Laws of information conservation (non-growth) and aspects of the foundation of probability theory. Problems Inform. Transmission, 10:206–210, 1974.



Kolmogorov's approach to probability theory
In 1970, Kolmogorov developed the 'Combinatorial foundations of information theory and the calculus of probabilities' in relation to a presentation at the International Congress of Mathematicians in Nice(1970). This text was eventually published in 1983:


* A.N. Kolmogorov. Combinatorial foundations of information theory and the calculus of probabilities. Russian Math. Surveys (1983).


While Kolmogorov admits that his treatment is incomplete, he presents strong arguments for the following conclusions:


1. Information theory must precede probability theory and not be based on it. By the very essence of this discipline, the foundations of information theory has a finite combinatorial character.
2. The applications of probability theory can be put on a uniform basis. It is always a matter of consequences of hypotheses about the impossibility of reducing in one way or another the complexity of the description of the objects in question.


In the last statement, Kolmogorov is implicitly referring to the Minimum Description Length or Kolmogorov Complexity of an object.


**Note:**


Since 1983, the important influence Kolmogorov's theory of Algorithmic Information has had on modern science may be partly determined by the scientific research direction of Deep Mind led by Shane Legg, whose Universal Intelligence Measure of an agent with policy $\pi$ is determined by the formula:


\begin{equation}
\Upsilon(\pi) := \sum\_{\mu \in E} 2^{-K(\mu)} V\_{\mu}^{\pi}
\end{equation}


where $E$ is the space of environments, $2^{-K(\mu)}$ is the algorithmic probability that an agent finds itself in this environment and $V\_{\mu}^{\pi}$ is the expected future discounted reward of an agent $\pi$ interacting with environment $\mu$. For the complete theory behind this formula, I may refer the reader to the PhD thesis of Shane Legg:


* Legg, Shane. Machine Super Intelligence (Thesis). Lugano, Switzerland: Università della Svizzera italiana. 2008.


This formula actually appears at 3:22 in the 2019 TED talk of Thore Graepel, a research scientist at Deep Mind, titled 'The human pursuit of artificial intelligence'.


