https://wiki.lesswrong.com/api.php?action=feedcontributions&user=Maha&feedformat=atomLesswrongwiki - User contributions [en]2020-09-23T03:12:30ZUser contributionsMediaWiki 1.31.8https://wiki.lesswrong.com/index.php?title=Algorithmic_complexity&diff=11824Algorithmic complexity2012-12-10T13:00:11Z<p>Maha: just standardizing the "Kolmogorov" spelling.</p>
<hr />
<div>{{wikilink|Kolmogorov complexity}}<br />
The '''Algorithmic Complexity''' or '''Kolmogorov Complexity''' of a set of data is the size of the shortest possible description of the data.<br />
<br />
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<ref>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. </ref>. If the data has few regular patterns, it is difficult to compress it or describe it shortly, giving it a high 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. <ref> FORTNOW, Lance. "Kolmogorov Complexity" Available at: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.120.4949&rep=rep1&type=pdf </ref><br />
<br />
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. <ref> LI, Ming. & VITANY, Paul. “Algorithmic Complexity”. Available at: http://homepages.cwi.nl/~paulv/papers/020608isb.pdf </ref><br />
<br />
This notion can be used to state many important results in computational theory. Possibly the most famous is [http://en.wikipedia.org/wiki/Kolmogorov_complexity#Chaitin.27s_incompleteness_theorem Chaitin's incompleteness theorem], a version of Gödel’s incompleteness theorem.<br />
<br />
==Blog Posts==<br />
*[http://lesswrong.com/lw/vh/complexity_and_intelligence/ Complexity and Intelligence]<br />
<br />
==References==<br />
{{Reflist|2}}<br />
<br />
<br />
==See also==<br />
* [[Solomonoff induction]]<br />
* [[AIXI]]</div>Maha