Kolmogorov complexity
The length of the shortest possible computer program that outputs a given string; a formal measure of how compressible the string is.
As defined in 320 | Solo: Complexity and the Universe
Where it comes up · 13
- 40 - Complexity Stupidity2 claims
- Lee Cronin2 claims
- 320 | Solo: Complexity and the Universe2 claims
- AMA | February 20252 claims
- Adam Marblestone – AI is missing something fundamental about the brain1 claim
- Dwarkesh Patel Podcast - Grant Sanderson – AI and the future of math1 claim
- Shane Legg (DeepMind Founder) — 2028 AGI, superhuman alignment, new architectures1 claim
- Part One: Complex World1 claim
and 5 more
Most important claims · 10 of 17Search all claims for “Kolmogorov complexity” →
- A truly random string of digits is incompressible — its description is as long as the sequence itself — but a coin-flip sequence can be described very briefly by describing the dynamics of the coin; in all such cases you should describe the underlying causal process that generates the pattern, not the observed pattern itself, which is a crucial distinction in complexity science.40 - Complexity Stupidity
- Complexity can be measured by the length of the shortest description that reliably captures what is interesting about a phenomenon: very regular objects (a crystal/cube) and very random objects (a gas) both have short descriptions, but complex phenomena like a mouse live between order and randomness and require very long descriptions — which is why complexity science is hard, since you can write e=mc² but you cannot write down a mouse.40 - Complexity Stupidity
- The phase transition can be measured by approximating the Kolmogorov complexity of the soup via compression: initially random bytes are incompressible (gas-like), but once replicators appear the soup becomes far more compressible because many tapes are pasted-together parts of other tapes, so complexity drops dramatically as the system shifts from an incompressible Turing gas to a structured computational phase.286 | Blaise Agüera y Arcas on the Emergence of Replication and Computation
- Apparent complexity, defined via coarse-graining then compression, is low both for a perfectly ordered string (e.g., a billion zeros, trivially compressible) and for a truly random string (whose coarse-grained averages are uniform), but high for an intermediate string that has structure yet is not fully ordered, because only such structure survives coarse-graining while resisting full compression.320 | Solo: Complexity and the Universe
- Understanding a system requires compressing it into a simpler description, which raises the possibility that the brain may be incompressible—meaning the only way to fully understand a brain is to be a brain, analogous to how perfectly simulating a universe would require something the size of the universe.AMA | February 2025
- If all possible worlds (or all mathematical structures, as in Tegmark's view) are equally real, then a world where gravity is inverse-square only until 2020 also exists, creating a measure problem: it becomes unclear why we should say our world probably isn't such a bent world, requiring some weighting like algorithmic simplicity to assign more weight to shorter descriptions.76 | Ned Hall on Possible Worlds and the Laws of Nature
- Kolmogorov complexity — the length of the shortest program that outputs a given string — is formally uncomputable because cycling through candidate programs runs into Turing's halting problem (one cannot generally tell whether a long-running program will ever halt), though it remains estimable in practice via compression algorithms like gzip.320 | Solo: Complexity and the Universe
- While 'complex' systems are hard to define, 'complicated' systems may be more tractable, and Kolmogorov complexity—the amount of information required to write down the full rules of a system—provides a reasonable measure of how complicated (as opposed to complex) a system is.AMA | February 2025
- Assembly theory is not about how compressed an object is; unlike computer-science compression which assumes instantaneous access to all information in memory, assembly theory requires that you cannot access a motif in memory until you have done the work to construct it along a causal chain.Lee Cronin
- Assembly theory differs from Kolmogorov complexity and algorithmic information theory because the latter require a Turing machine and ignore causation, only telling you about dataset compression; assembly theory captures the causal chain by which an object emerged, and algorithmic information theory is actually a subset of assembly theory because selection produces the factories and computers from which it arises.Lee Cronin