Ruby | v1.9.0Sep 15th 2020 | (+36/-32) | ||

Maha | v1.8.0Dec 10th 2012 | (+10/-10) just standardizing the "Kolmogorov" spelling. | ||

Kaj_Sotala | v1.7.0Sep 13th 2012 | (+238/-405) | ||

joaolkf | v1.6.0Sep 12th 2012 | (+5) | ||

joaolkf | v1.5.0Sep 12th 2012 | (+26/-26) | ||

joaolkf | v1.4.0Sep 12th 2012 | (+21/-21) | ||

joaolkf | v1.3.0Sep 12th 2012 | |||

joaolkf | v1.2.0Sep 12th 2012 | moved [[Kolmogorov complexity]] to [[Algorithmic complexity]]: same concept | ||

joaolkf | v1.1.0Sep 12th 2012 | (+1712) | ||

Vladimir_Nesov | v1.0.0May 15th 2011 | (+32) page stub |

The **Algorithmic Complexity** or **Kolmogorov Complexity** of a set of data is the size of the shortest possible description of the data.*See also*: Solomonoff Induction, AIXI

- SIPSER, M. (1983) "A complexity theoretic approach to randomness". In Proceedings of the 15th ACM Symposium on the Theory of Computing, pages 330{335. ACM, New York.↩
- FORTNOW, Lance. "Kolmogorov Complexity" Available at: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.120.4949&rep=rep1&type=pdf↩
- LI, Ming. & VITANY, Paul. “Algorithmic Complexity”. Available at: http://homepages.cwi.nl/~paulv/papers/020608isb.pdf↩

Algorithmic complexity is an inverse measure of compressibility. If the data is complex and random, the shortest possible description of it becomes longer. This is also one of the best definitions of randomness so far^{1}. If the data has few regular patterns, it is difficult to compress it or describe it shortly, giving it a high ~~Kolmogorow~~Kolmogorov complexity and randomness. If there isn't any way to describe the data so that the description is shorter than the data itself, the data is incompressible. ^{2}

The **Algorithmic Complexity** or **Kolmogorov Complexity** of a set of data is the size of the shortest possible description of ~~this~~the data.~~ It’s~~

Algorithmic complexity is an inverse measure of compressibility. ~~How much more~~If the data is ~~needed to make~~complex and random, the shortest ~~description, more complex and random the data is.~~possible description of it becomes longer. This is also one of the best ~~accounts~~definitions of randomness so far^{1}. ~~As~~If the ~~numbers of patterns in the date increases, more ways to compress it, describe~~data has few regular patterns, it ~~shortly, and there are less Kolmogorov Complexity and less randomness. As the number of patterns in the date decreases, less ways~~is difficult to compress it or describe it shortly, ~~so there are more Kolmogorov~~giving it a high Kolmogorow complexity and randomness. ~~In the limit situation,~~If there ~~isn’~~isn't ~~a single~~any way to describe the data ~~which takes less space~~so that the description is shorter than the data itself, the data is incompressible. ^{2}

This notion can be used to state many important results in computational theory. ~~The~~Possibly the most ~~famous, perhaps,~~famous is Chaitin's incompleteness theorem, a version of Gödel’s incompleteness theorem.

The **Algorithmic Complexity** or **Kolmogorov Complexity** of a set of data is the size of the shortest possible description of this data. It’s an inverse measure of compressibility. How much more data is needed to make the shortest description, more complex and random the data is. This is also one of the best accounts of randomness so far^{1}. As the numbers of patterns in the date increases, more ways to compress it, describe it shortly, and there are less Kolmogorov Complexity and less randomness. As the number of patterns in the date decreases, less ways to compress it or describe it shortly, so there are more Kolmogorov complexity and randomness. In the limit situation, there isn’t a single way to describe the data which takes less space than the data itself, the data is incompressible. ^{2}

The **Algorithmic Complexity** or **Kolmogorov Complexity** of a set of data is the size of the shortest possible description of data. It’s an inverse measure of compressibility. How much more data is needed to make the shortest description, more complex and random the data is. This is ~~also,~~also one of the best accounts of randomness so far^{1}. As the numbers of patterns in the date increases, more ways to compress it, describe it ~~shortly there are,~~shortly, and there are less Kolmogorov Complexity and less randomness. As the number of patterns in the date decreases, less ways to compress it or describe it shortly, so there are more Kolmogorov complexity and randomness. In the limit situation, there isn’t a single way to describe the data which takes less space than the data itself, the data is incompressible. ^{2}

This notion can be used to state many important results in computational theory. The most famous, perhaps, ~~are~~is Chaitin's incompleteness theorem, a version of Gödel’s incompleteness theorem.

The ** KolmogorovAlgorithmic Complexity** or

The **Kolmogorov Complexity** or **Algorithmic Complexity** of a set of data is the shortest possible description of data. It’s an inverse measure of compressibility. How much more data is needed to make the shortest description, more complex and random the data is. This is also, one of the best accounts of randomness so far^{1}. As the numbers of patterns in the date increases, more ways to compress it, describe it shortly there are, and there are less Kolmogorov Complexity and less randomness. As the number of patterns in the date decreases, less ways to compress it or describe it shortly, so there are more Kolmogorov complexity and randomness. In the limit situation, there isn’t a single way to describe the data which takes less space than the data itself, the data is incompressible. ^{2}

More formally, the Kolmogorov complexity C(x) of a set x, is the size in bits of the shortest binary program (in a fixed programming language) that prints the set x as its only output. If C(x) is equal or greater than the size of x in bits, x is incompressible. ^{3}

This notion can be used to state many important results in computational theory. The most famous, perhaps, are Chaitin's incompleteness theorem , a version of Gödel’s incompleteness theorem.

- SIPSER, M. (1983) "A complexity theoretic approach to randomness". In Proceedings of the 15th ACM Symposium on the Theory of Computing, pages 330{335. ACM, New York.↩
- FORTNOW, Lance. "Kolmogorov Complexity" Available at: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.120.4949&rep=rep1&type=pdf↩
- LI, Ming. & VITANY, Paul. “Algorithmic Complexity”. Available at: http://homepages.cwi.nl/~paulv/papers/020608isb.pdf↩