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


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


  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.

  • 2
    $\begingroup$ It would help me if you'd expand your question. We all know that Kolmogorov did a lot of work on algorithmic information theory, but you seem to be thinking of something very specific when you say "axioms for probability theory". What? Do you have a reference? $\endgroup$
    – usul
    Sep 11, 2022 at 19:25
  • $\begingroup$ It seems odd to answer your own question just one day after it was asked; it feels a little like the question was asked just so the answer you gave could be publicized $\endgroup$
    – Yemon Choi
    Oct 15, 2022 at 13:59
  • 1
    $\begingroup$ @YemonChoi As I don't read/write in Russian and I don't have access to Kolmogorov's works that were published posthumously, I didn't expect my answer to be the final answer. $\endgroup$ Oct 16, 2022 at 10:06

2 Answers 2


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.


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


Certainly not. Simple comparison of the dates shows this. Kolmogorov axiomatics for probability theory was published in 1933.

Kolmogoroff, A. Grundbegriffe der Wahrscheinlichkeitsrechnung. Ergebnisse der Mathematik und ihrer Grenzgebiete 2, Nr. 3. Berlin: Julius Springer. IV + 62 S. (1933).

  • 7
    $\begingroup$ The question was this: "Did Kolmogorov develop a set of axioms for probability theory motivated by Algorithmic Information Theory in the 1960s?" I know of no evidence that Kolmogorov was motivated by algorithmic information theory in the 1930s. Do you? $\endgroup$ Sep 11, 2022 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.