Metraipolis › archive › dc_41bb503c416c
Kolmogorov complexity — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/Kolmogorov_complexity
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-07T18:56:38.394Z
- SHA-256 of the archived text
8a6cf21caf805230da053d1c226e138d21f89c2a66b05eb4f4ac4d6904801f30- Stable URL of this page
https://metraipolis.com/documento/dc_41bb503c416c
How to cite
Kolmogorov complexity — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Kolmogorov_complexity (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_41bb503c416c (Metraipolis archive dc_41bb503c416c, sha256 8a6cf21caf805230da053d1c226e138d21f89c2a66b05eb4f4ac4d6904801f30)
BibTeX
@misc{dc41bb503c416c,
title = {Kolmogorov complexity — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/Kolmogorov_complexity},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_41bb503c416c; sha256 8a6cf21caf805230da053d1c226e138d21f89c2a66b05eb4f4ac4d6904801f30},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Kolmogorov_complexity. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program (in a predetermined programming language) that produces the object as output. It is a measure of the computational resources needed to specify the object, and is also known as algorithmic complexity, Solomonoff–Kolmogorov–Chaitin complexity, program-size complexity, descriptive complexity, or algorithmic entropy. It is named after Andrey Kolmogorov, who first published on the subject in 1963 and is a generalization of classical information theory. The notion of Kolmogorov complexity can be used to state and prove impossibility results akin to Cantor's diagonal argument, Gödel's incompleteness theorem, and Turing's halting problem. In particular, no program P computing a lower bound for each text's Kolmogorov complexity can return a value essentially larger than P's own length (see section § Chaitin's incompleteness theorem); hence no single program can compute the exact Kolmogorov complexity for infinitely many texts. Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «information theory»). Fonte: Wikipedia in inglese, voce «Kolmogorov complexity» — https://en.wikipedia.org/wiki/Kolmogorov_complexity Wikidata Q1456811 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1456811 Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Kolmogorov_complexity?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 1376466730, consultata il 2026-10-07T18:15:34.839Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 90a6eff3e4ba39f5db09f6124b47fe6a9f6846f4d0dfc245d6505418681d8a42