Source-linked AI summary
Algorithmic Information Theory: a brief non-technical guide to the field
Marcus Hutter
TL;DR
AIT addresses how to define information and randomness objectively for individual objects by combining information theory with computation theory. This guide organizes the field around algorithmic complexity, universal probability, search, and randomness, and surveys its applications. It concludes that AIT has broad applications despite incomputable core concepts, while practical approximations have difficult-to-assess accuracy and can invalidate many theorems.
Problem
AIT seeks an objective notion of information and randomness for individual objects, beyond classical information theory’s focus on random variables and communication.
Method
The article presents a brief guide to AIT’s core concepts, subfields, history, applications, and field map, including complexity, universal probability, search, and randomness.
Results
AIT provides formal notions of information and individual-object randomness, with applications including universal similarity metrics and automated reconstruction of language and phytogenetic trees.
Takeaways & Limitations
AIT’s concepts have often unexpected applications, and normalized compression distance has supported fully automatic reconstruction and clustering tasks.
Takeaways & Limitations
Practical approximations are difficult to assess for accuracy, and most AIT theorems break down when universal machines are replaced by limited problem-adapted machines.
Abstract
from arXiv · showhide
This article is a brief guide to the field of algorithmic information theory (AIT), its underlying philosophy, and the most important concepts. AIT arises by mixing information theory and computation theory to obtain an objective and absolute notion of information in an individual object, and in so doing gives rise to an objective and robust notion of randomness of individual objects. This is in contrast to classical information theory that is based on random variables and communication, and has no bearing on information and randomness of individual objects. After a brief overview, the major subfields, applications, history, and a map of the field are presented.
1 Overview
AIT combines information theory and computation theory to measure information and randomness in individual objects. Its core concepts include shortest descriptions, universal probabilities, computable search variants, and formal individual-string randomness.
- AIT studies the relationship between computation, information, and randomness in individual objects.
- Algorithmic complexity measures an object by the length of its shortest program that computes or outputs it.
- Algorithmic Solomonoff Probability assigns probabilities through the outputs of a universal computer fed randomly chosen programs.
- Because algorithmic complexity and probability are incomputable, Levin complexity and Universal Levin Search provide computable variants and optimal inversion-time guarantees up to a large multiplicative constant.
- Algorithmic Martin-Loef Randomness defines an individual string as random when it is incompressible, with complexity equal to its length.
- AIT underlies Minimum Description Length, contributes to computational complexity theory, defines universal similarity metrics, and addresses the Maxwell demon problem.
2 Algorithmic “Kolmogorov” Complexity (AC)
Algorithmic Kolmogorov Complexity formalizes simplicity as the shortest effective description produced by a universal computer. The prefix variant supports conditional complexity, coding properties, and bounds that characterize compressibility and information structure.
- Algorithmic complexity treats a string as simple when a short effective description exists and complex when its shortest description is long.
- A program p describes x when running p on universal computer U outputs x; the shortest such program determines K(x).
- The choice of universal computer changes K(x) by at most an additive constant independent of x.
- Plain and prefix complexity are major variants, and most variants differ only by an additive term logarithmic in string length.
- Prefix complexity uses a universal prefix Turing machine whose halting program is the scanned input prefix and whose output is the written string.
- For conditional complexity, K(x|y) is the shortest binary program producing x on U when supplied with input y.
- K is upper-semicomputable but not computable, while its properties include upper bounds, subadditivity, symmetry of information, and non-increase under computable functions.
- For prefix complexity, K(x) is at least the string length for most x, while K(x) is bounded by log x + 2 log log x + c for all integer-interpreted strings.
3 Algorithmic “Solomonoff” Probability (AP)
Algorithmic Solomonoff Probability formalizes prior plausibility by combining universal computation, Occam’s razor, multiple explanations, and Bayesian updating. Its predictive distribution converges on computable sequences and supports strong prediction and decision-making results.
- Solomonoff Probability is the probability that a universal computer outputs a string when given a randomly chosen program.
- Its framework combines Occam’s razor, multiple consistent explanations, Bayes’s Rule, universal Turing machines, and algorithmic complexity.
- Using K as complexity, simpler strings receive higher a priori plausibility through a monotone decreasing function such as 2^-K(x).
- The universal a priori probability M(x) sums weights of minimal programs whose outputs start with x, so shortest programs dominate and M(x) is roughly 2^-K(x).
- M’s predictive distribution converges rapidly to 1 on any computable sequence and provides excellent predictions and decisions in general stochastic environments.
- Combined with sequential decision theory, M yields an optimal reinforcement learning agent in an arbitrary unknown environment and a formal test of intelligence.
- Chaitin’s constant Ω is the probability that a universal computer halts on fair-coin input and can quantify Gödel’s Incompleteness Theorem.
4 Universal “Levin” Search (US)
Universal Search (US) extends parallel execution from two algorithms to all programs, while Levin complexity makes the resulting time-bounded approach computable. In theory it achieves near-optimal inversion time, but practical use is limited by large hidden constants and verification requirements.
- Universal Search: US runs candidate algorithms in parallel and returns the first verified solution, achieving performance close to the fastest candidate.For two algorithms, emulating each at half-speed gives a factor-of-two overhead relative to the faster algorithm.
- Universal Search: US extends this strategy to infinitely many programs by allocating each prefix program p a time fraction of 2^-l(p).It verifies outputs and discards programs that do not solve the problem.
- Levin Complexity: Levin complexity addresses AC’s incomputability by adding the logarithm of a program’s running time to its description length.This time penalty yields computable variants of algorithmic complexity and probability.
- Levin Complexity: Kt(x) is the logarithm of US’s running time without verification and is therefore computable.The correspondence links the time-bounded complexity measure directly to universal search.
- Practical limits: US is not practically applicable in its basic form because its running time has huge hidden multiplicative constants and verification must be fast.Later approaches reduce some restrictions, but may introduce larger additive constants or require carefully designed practical variants.
5 Algorithmic “Martin-Loef” Randomness (AR)
Algorithmic Martin-Löf Randomness (AR) formalizes randomness for individual sequences through all effectively testable randomness requirements. For infinite sequences, this is equivalent to incompressibility of every initial segment, connecting randomness with the absence of regularities.
- Motivation: Classical probability axioms do not determine whether a specific individual object or observation is random.Their standard interpretations concern probability semantics rather than randomness of particular binary strings.
- Definition: Martin-Löf randomness uses constructive, effectively testable requirements to formalize randomness.The tests are derived from Turing machines and can be effectively enumerated.
- Definition: AR sequences satisfy all such tests, and the collection of sequences satisfying them has measure one.This follows because there are countably many tests, each with a measure-one set of satisfying sequences.
- Characterization: For infinite sequences, AR is equivalent to every initial segment being incompressible: its prefix complexity is at least its length.This gives a complexity-based characterization of the test-based definition.
- Interpretation: Compression corresponds to regularity and therefore to non-randomness in the intuitive characterization of strings.The article states that a string is compressible if and only if it has regularities, and non-random if and only if it has regularities.
- Further properties: ML-random sequences cannot be effectively constructed, although the binary expansion of the halting probability Ω provides a natural example.The passage also notes that randomness can be defined for objects beyond strings and sequences.
6 Applications of AIT
AIT applies its formal notions of information, complexity, and randomness across philosophy, science, theoretical computer science, and practical data analysis. Its most successful practical application is a compression-based similarity metric, while approximations remain difficult to assess reliably.
- Philosophy: AIT formalizes and quantifies vague concepts such as simplicity, complexity, and randomness, enabling more rigorous philosophical analysis.Algorithmic complexity gives simplicity and complexity an essentially unique quantitative formalization.
- Philosophy: Using algorithmic complexity to quantify simplicity supports universal theories of induction and action based on Occam’s razor.Solomonoff and others use this formalization in artificial intelligence.
- Physics: AIT contributes to thermodynamics by helping address entropy increase and the Maxwell demon problem.The passage places this application in the foundations of thermodynamics.
- Practice: Practical AIT replaces the universal Turing machine with limited machines adapted to particular problems, but approximation accuracy is hard to assess.The passage warns that most AIT theorems break down under these approximations.
- Practice: The universal similarity metric defines similarity through the difficulty of transforming one object into another.Approximating K with compressors yields normalized compression distance, used for automatically reconstructing language and phylogenetic trees and for clustering.
- Science: AIT has influenced theoretical computer science, statistics, cognitive sciences, biology, physics, and economics.In theoretical computer science, the incompressibility method has resolved open problems and simplified proofs.
- Practice: MDL can be viewed as a downscaled practical version of algorithmic complexity.This connects an ideal AIT concept with a practical machine-learning principle.
7 History, References, Notation, Nomenclature
AIT emerged in the 1960s from work by Kolmogorov, Solomonoff, and Chaitin, with major contributions by Levin in the 1970s. Its terminology and even its name remain unsettled across mathematical, logical, and computer-science traditions.
- History: Kolmogorov proposed shortest-program information content, while Solomonoff developed universal a priori probability and applied it to time-series forecasting.Together with Chaitin, their work initiated AIT in the 1960s.
- History: Levin and others made significant contributions in the 1970s, including prefix complexity and time-bounded complexity.These developments expanded the field’s core technical concepts.
- References: Li and Vitanyi’s book is identified as the standard AIT textbook, while other references focus on AC and AR, AP and US, or AR.The article points readers to an AIT website for further references and field information.
- Notation and nomenclature: AIT lacks generally agreed notation and nomenclature because researchers from different backgrounds entered the field and many definitions have multiple inventors or variants.The article therefore uses descriptive names with contributors in quotation marks.
- Notation and nomenclature: The field itself is variously called Algorithmic Information Theory or the narrower, more personal term Kolmogorov complexity.The article favors Algorithmic Information Theory because it is descriptive and impersonal.
8 Map of the Field
The field map divides AIT into about four subfields: algorithmic complexity, algorithmic probability, universal search, and algorithmic randomness/recursion theory. It also connects AIT to randomness concepts and applications including machine learning, artificial intelligence, and information theory.
- Algorithmic “Kolmogorov” Complexity (AC) covers philosophical considerations, complexity properties, and plain, prefix, resource-bounded, and other variants.
- Algorithmic “Solomonoff” Probability (AP) includes algorithmic probability, universal sequence prediction, and Chaitin’s Omega.
- Universal “Levin” Search (US) covers Levin search, Levin complexity, speed priors, adaptive search, and optimal problem-solving systems.
- Algorithmic “Martin-Loef” Randomness (AR) is presented alongside recursion theory.
- The map links AIT to randomness of reals, effective Hausdorff dimension, machine learning, artificial intelligence, computational complexity, and Shannon information theory.