Solomonoff Induction and Singular Integrals
Abstract
The Solomonoff distribution M assigns an a priori probability to a finite binary string z by summing over all programs whose output begins with z, weighting a program of length ℓ by 2−ℓ. Thus, likely strings are those with many short explanations. This appears to be a purely discrete notion of complexity. However, Riemann sums are also countable. We show that the sum defining M, suitably reorganised, contains Riemann sums approximating the Bayesian evidence of any computable statistical model. These evidence integrals are singular integrals whose asymptotics are governed by Singular Learning Theory and, through it, by invariants of algebraic geometry. Concretely, for every computable Bayesian model, we construct a single monotone Turing machine whose induced semimeasure agrees with the evidence Zn up to a uniform multiplicative constant. If the model also satisfies the hypotheses of Watanabe's free-energy asymptotics, then a sample Xn=X1⋯ Xn drawn i.i.d. from the true distribution satisfies −log M(Xn) ≤ nLn(w0)+λlog n−(m−1)loglog n+Oℙ(1), where Ln is the empirical loss, w0 is an optimal parameter, λ is the learning coefficient, and m is its multiplicity. Thus the learning coefficient, a geometric measure of model simplicity, appears within the Solomonoff distribution as the coefficient of log n in an upper bound on code length.
Related
- What Can Language Models Inherit from Solomonoff Induction? Limits, Attainable Properties, and What Served Conditionals Reveal
- Solomonoff induction of selected bits and online classification
- Approximate Solomonoff Induction: On the Robustness of Learned Universal Predictors
- The Singular Set of Minima of Multiple Integrals
- Weak type (1,1) estimates for noncommutative maximal truncated rough singular integrals
BibTeX
@misc{troiani2026solomonoff,
title = {{Solomonoff Induction and Singular Integrals}},
author = {Will Troiani and Daniel Murfet},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.01666},
eprint = {2609.01666},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.01666},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Solomonoff Induction and Singular Integrals
AU - Will Troiani
AU - Daniel Murfet
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.01666
UR - https://arxiv.org/abs/2609.01666
AB - The Solomonoff distribution M assigns an a priori probability to a finite binary string z by summing over all programs whose output begins with z, weighting a program of length ℓ by 2^−ℓ. Thus, likely strings are those with many short explanations. This appears to be a purely discrete notion of complexity. However, Riemann sums are also countable. We show that the sum defining M, suitably reorganised, contains Riemann sums approximating the Bayesian evidence of any computable statistical model. These evidence integrals are singular integrals whose asymptotics are governed by Singular Learning Theory and, through it, by invariants of algebraic geometry. Concretely, for every computable Bayesian model, we construct a single monotone Turing machine whose induced semimeasure agrees with the evidence Z_n up to a uniform multiplicative constant. If the model also satisfies the hypotheses of Watanabe's free-energy asymptotics, then a sample X^n=X_1⋯ X_n drawn i.i.d. from the true distribution satisfies −log M(X^n) ≤ nL_n(w_0)+λlog n−(m−1)loglog n+O_ℙ(1), where L_n is the empirical loss, w_0 is an optimal parameter, λ is the learning coefficient, and m is its multiplicity. Thus the learning coefficient, a geometric measure of model simplicity, appears within the Solomonoff distribution as the coefficient of log n in an upper bound on code length.
ER -