Kolmogorov's Algorithmic Mutual Information Is Equivalent to Bayes' Law
Pith reviewed 2026-05-25 12:20 UTC · model grok-4.3
The pith
Kolmogorov's algorithmic mutual information between any two strings is symmetric, forming the algorithmic version of Bayes' law.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Kolmogorov's notion of algorithmic information, which is based on the theory of algorithms, proposes an objective measure of the amount of information in a finite string about itself and concludes that for any two finite strings x and y, the amount of information in x about y is almost equal to the amount of information in y about x. We view this conclusion of Kolmogorov as the algorithmic information version of Bayes' law. This can be easily demonstrated if one considers the work of Levin on prefix Kolmogorov complexity and then expresses the amount of Kolmogorov mutual information between two finite strings using Solomonoff's a priori probability.
What carries the argument
Rewriting Kolmogorov mutual information via Solomonoff's a priori probability and Levin's prefix complexity to expose the symmetry.
If this is right
- Algorithmic learning from finite strings inherits the symmetry property of Bayes' law.
- Mutual information between strings supplies an objective update rule for beliefs consistent with observations.
- Solomonoff's universal semimeasure can replace probabilistic priors while preserving Bayes-like symmetry.
- The equivalence holds for any pair of finite strings without requiring additional constraints on the strings.
Where Pith is reading between the lines
- This symmetry may imply that compression-based methods automatically satisfy reciprocal information properties in practice.
- The result could connect algorithmic information theory to minimum description length approaches in model selection.
- It raises the possibility of deriving other probabilistic identities directly from prefix complexity expressions.
Load-bearing premise
That rewriting algorithmic mutual information in terms of Solomonoff's universal semimeasure produces a quantity whose symmetry directly mirrors the probabilistic form of Bayes' law without further assumptions on the strings or the choice of universal machine.
What would settle it
Two concrete finite strings x and y for which the Kolmogorov mutual information I(x:y) computed under a fixed universal machine differs by more than a small additive constant from I(y:x).
read the original abstract
Given two events $A$ and $B$, Bayes' law is based on the argument that the probability of $A$ given $B$ is proportional to the probability of $B$ given $A$. When probabilities are interpreted in the Bayesian sense, Bayes' law constitutes a learning algorithm which shows how one can learn from a new observation to improve their belief in a theory that is consistent with that observation. Kolmogorov's notion of algorithmic information, which is based on the theory of algorithms, proposes an objective measure of the amount of information in a finite string about itself and concludes that for any two finite strings $x$ and $y$, the amount of information in $x$ about $y$ is almost equal to the amount of information in $y$ about $x$. We view this conclusion of Kolmogorov as the algorithmic information version of Bayes' law. This can be easily demonstrated if one considers the work of Levin on prefix Kolmogorov complexity and then expresses the amount of Kolmogorov mutual information between two finite strings using Solomonoff's a priori probability.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript claims that Kolmogorov's conclusion on the near-symmetry of algorithmic mutual information (the amount of information in x about y is almost equal to that in y about x) constitutes the algorithmic version of Bayes' law, and that this equivalence can be easily demonstrated by expressing Kolmogorov mutual information using Solomonoff's a priori probability after considering Levin's prefix complexity.
Significance. A rigorous demonstration linking algorithmic mutual information symmetry to Bayes' law would provide a novel bridge between algorithmic information theory and Bayesian updating. The manuscript, however, supplies no equations, definitions, or derivation steps, rendering the central claim unverifiable from the text.
major comments (2)
- [Abstract] Abstract: The assertion that the equivalence 'can be easily demonstrated' by expressing the mutual information via Solomonoff's a priori probability is unsupported, as the manuscript provides neither explicit definitions of the quantities involved nor any proof steps or equations.
- The proposed demonstration route does not establish the claimed symmetry. Using the standard conditional M(x|y) := M(xy)/M(x) yields M(x|y)M(y) = M(xy)M(y)/M(x), which equals M(y|x)M(x) only if M(x)=M(y). This condition fails for arbitrary strings, so the Bayes-like functional equality does not follow directly from the rewriting (in contrast to the separate Symmetry of Information theorem for prefix complexity K, which holds only up to O(log) additive terms).
minor comments (1)
- [Abstract] Abstract: The informal phrasing of Kolmogorov's conclusion could be replaced by the precise statement of the Symmetry of Information result (I(x;y) = K(x) - K(x|y*) ≈ K(y) - K(y|x*) up to logarithmic terms) to clarify what is being equated to Bayes' law.
Simulated Author's Rebuttal
We thank the referee for the detailed review. The manuscript is concise and does not include explicit equations or derivations, which limits verifiability as noted. We address each major comment below and indicate where revisions will be made.
read point-by-point responses
-
Referee: [Abstract] Abstract: The assertion that the equivalence 'can be easily demonstrated' by expressing the mutual information via Solomonoff's a priori probability is unsupported, as the manuscript provides neither explicit definitions of the quantities involved nor any proof steps or equations.
Authors: We agree that the manuscript as written provides no explicit definitions or derivation steps, rendering the central claim difficult to verify from the text alone. A revised version will include the definitions of Levin prefix complexity, Solomonoff's universal semimeasure M, the expression of algorithmic mutual information in terms of M, and the explicit steps showing how the near-symmetry follows and constitutes the algorithmic counterpart to Bayes' law. revision: yes
-
Referee: [—] The proposed demonstration route does not establish the claimed symmetry. Using the standard conditional M(x|y) := M(xy)/M(x) yields M(x|y)M(y) = M(xy)M(y)/M(x), which equals M(y|x)M(x) only if M(x)=M(y). This condition fails for arbitrary strings, so the Bayes-like functional equality does not follow directly from the rewriting (in contrast to the separate Symmetry of Information theorem for prefix complexity K, which holds only up to O(log) additive terms).
Authors: The standard definition of the conditional semimeasure is M(x|y) := M(xy)/M(y). Substituting this yields M(x|y)M(y) = M(xy) exactly, and likewise M(y|x)M(x) = M(xy), so the equality M(x|y)M(y) = M(y|x)M(x) holds for arbitrary strings. This is the direct algorithmic analogue of Bayes' law. Algorithmic mutual information is then expressed as I(x:y) ≈ −log M(x) + log M(x|y) (via the relation K(z) ≈ −log M(z)), and the equality above ensures I(x:y) ≈ I(y:x). We therefore disagree that the proposed route fails to establish the symmetry; the calculation in the comment relies on a nonstandard definition of the conditional. revision: no
Circularity Check
No significant circularity; interpretive re-expression of known symmetry
full rationale
The paper asserts that Kolmogorov's observed near-symmetry I(x;y) ≈ I(y;x) constitutes the algorithmic analogue of Bayes' law and states that this can be demonstrated by rewriting Kolmogorov mutual information in terms of Solomonoff's a priori semimeasure M and Levin prefix complexity. This is a single interpretive identification rather than a multi-step derivation whose central equality is forced by re-using the target quantity as an input or by a self-citation chain. No equations are supplied that define one side of the claimed equivalence in terms of the other, no parameters are fitted to a subset and then relabeled as a prediction, and the cited prior results (Levin, Solomonoff) are external to the present manuscript. The argument is therefore self-contained as a renaming of an independently established theorem and receives score 0.
Axiom & Free-Parameter Ledger
axioms (2)
- standard math Prefix Kolmogorov complexity is defined via Levin's prefix-free machines.
- standard math Solomonoff's a priori probability is the universal semimeasure over strings.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.