Algorithmic Information Theory Using Kolmogorov Complexity

[摘要] We are faced with the task of storing and communicating increasingly huge amounts of information. The development of digital storagemedia and communication channels have not been able to keep up withthis increasing demand in an economically viable way. Data compression is fast emerging as the key technique in resolving this technologicalissue. Kolmogorov complexity is the central tool used in this analysis.Informally the Kolmogorov complexity of an object is the length of theshortest string from which the original can be reconstructed lossless bya general-purpose computer. Thus the Kolmogorov complexity of anobject measures the maximum amount of compression that any losslesscompression program can achieve in theory. The main issue in translating theory to application is the fact that Kolmogorov complexity isnon-computable. This means that no computer program can computeprecisely the Kolmogorov complexity of a given string. FortunatelyKolmogorov complexity can be approximated by a computer, and thishas been used as the standard method of implementing classificationtechniques.