Algorithmic Information Theory

← Back to Domain-Specific Abstractions by Domain

3 domain-specific abstractions whose origin domain is Algorithmic Information Theory.

• Incompressibility method — A proof method that selects a Kolmogorov-incompressible object and shows that failure of the desired property would yield an impossibly shorter description.
• Kolmogorov complexity — The length of the shortest program for a fixed universal description language that outputs a given finite object and halts.
• Sophistication (complexity theory) — An algorithmic-information measure of the shortest model in which a string is a typical member at a declared significance tolerance.