Kolmogorov complexity
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.
- Comment
- enIn 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.
- Depiction
- Has abstract
- enIn 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 ); hence no single program can compute the exact Kolmogorov complexity for infinitely many texts.
- Hypernym
- Length
- Is primary topic of
- Kolmogorov complexity
- Label
- enKolmogorov complexity
- Link from a Wikipage to an external page
- www.csse.monash.edu.au/~dld
- tromp.github.io/cl/cl.html
- archive.org/details/courseinmathemat0000bell
- web.archive.org/web/20150215210504/http:/www.cs.umaine.edu/~chaitin/
- web.archive.org/web/20180321163508/http:/kolmogorov.com/
- archive.org/details/introductiontoth00sips
- homepages.cwi.nl/~paulv/kolmogorov.html
- www.idsia.ch/~juergen/kolmogorov.html
- www.csse.monash.edu.au/~dld/MML.html
- www.csse.monash.edu.au/~dld/Occam.html
- www.idsia.ch/~juergen/ray.html
- Link from a Wikipage to another Wikipage
- Algorithmically random sequence
- Algorithmic information theory
- Algorithmic probability
- Andrey Kolmogorov
- ASCII
- Axiomatic system
- Bayesian probability
- Berry's paradox
- Berry paradox
- Big-O notation
- Bit
- Blum axioms
- Cantor's diagonal argument
- Category:Algorithmic information theory
- Category:Computability theory
- Category:Computational complexity theory
- Category:Descriptive complexity
- Category:Information theory
- Category:Measures of complexity
- Chaitin's constant
- Chris Wallace (computer scientist)
- Code golf
- Complexity
- Computable function
- Computation
- Computer program
- Computer science
- Data compression
- Data structure
- Descriptive complexity theory
- Entropy (information theory)
- File:Kolmogorov complexity and computable lower bounds svg.svg
- File:Mandelpart2 red.png
- Formal system
- Full employment theorem
- Gödel's incompleteness theorem
- Gödel numbering
- Grammar induction
- Gregory Chaitin
- Halting problem
- Incompressible string
- Indirect argument
- Inductive inference
- Interpreter (computing)
- Java (programming language)
- Juergen Schmidhuber
- Kolmogorov structure function
- Leonid Levin
- Levenshtein distance
- Lisp programming language
- List of important publications in theoretical computer science
- Lower bound
- Marcus Hutter
- Markov information source
- Martingale (probability theory)
- Mathematics
- Matthew effect (sociology)
- Measure theory
- Ming Li
- Multiple discovery
- Mutual information
- Natural number
- Pascal (programming language)
- Pigeonhole principle
- Probability
- Programming language
- Proof by contradiction
- Proof of impossibility
- Q.E.D.
- Randomness
- Ray Solomonoff
- Sample entropy
- Self-delimiting program
- Self-extracting archive
- Solomonoff's theory of inductive inference
- String (computer science)
- Turing complete
- Turing degree
- Turing machine
- Uniform distribution (discrete)
- Universal Turing machine
- Up to
- SameAs
- Complejidad de Kolmogórov
- Complessità di Kolmogorov
- Complexidade de Kolmogorov
- Complexidade de Kolmogorov
- Complexitat de Kolmogórov
- Complexité de Kolmogorov
- Kolmogorov-complexiteit
- Kolmogorov complexity
- Kolmogorovi keerukus
- Kolmogorov karmaşıklığı
- Kolmogorovkomplexitet
- Kolmogorovská složitost
- Kolmogorow-Komplexität
- Kompleksitas Kolmogorov
- m.0rqy
- Q1456811
- Tsac
- Złożoność Kołmogorowa
- Колмогоровская сложность
- Колмогоровська складність
- סיבוכיות קולמוגורוב
- تعقيد كولموغروف
- پیچیدگی کولموگروف
- コルモゴロフ複雑性
- 柯氏复杂性
- 콜모고로프 복잡도
- SeeAlso
- Algorithmic randomness
- Subject
- Category:Algorithmic information theory
- Category:Computability theory
- Category:Computational complexity theory
- Category:Descriptive complexity
- Category:Information theory
- Category:Measures of complexity
- Thumbnail
- WasDerivedFrom
- Kolmogorov complexity?oldid=1124800985&ns=0
- WikiPageLength
- 41196
- Wikipage page ID
- 1635
- Wikipage revision ID
- 1124800985
- WikiPageUsesTemplate
- Template:Cite book
- Template:Cite journal
- Template:Cite web
- Template:Color
- Template:Compression Methods
- Template:Expand section
- Template:Isbn
- Template:Main
- Template:Mathematical logic
- Template:Reflist
- Template:Rp
- Template:See also
- Template:Short description
- Template:Slink
- Template:Val
