Reproduce “Towards a stable definition of Kolmogorov-Chaitin complexity” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Jean-Paul Delahaye, Hector Zenil
This research addresses the practical instability of Kolmogorov-Chaitin complexity (K) by empirically demonstrating that fundamental computational models produce output probability distributions that are statistically correlated and show convergence towards a stable "natural distribution." The approach introduces a quantifiable criterion for identifying "natural" computational models that yield more robust K approximations, particularly for short strings, where the additive constant's influence is most pronounced.
Key insights
- Fundamental computational models, despite their inherent structural differences, exhibit strong and statistically significant correlations in their empirically derived output probability distributions for strings up to length 12.
- This observed correlation and order preservation suggests that these models are 'c-Kolmogorov-Chaitin monotone,' indicating a tendency to converge towards a common, stable 'natural probability distribution' which can serve as a reference for K.
- The research provides an empirical definition of 'naturalness' in computational models, moving beyond subjective notions by linking it to the statistical convergence and order-preserving properties of their generated string distributions.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.