Kolmogorov complexity (original) (raw)

(definition)

**Definition:**The minimum number of bits into which a string can be compressed without losing information. This is defined with respect to a fixed, but universal decompression scheme, given by a universal Turing machine.

See also incompressible string.

Note: From Algorithms and Theory of Computation Handbook, page 29-20, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

More information

Special issue of the Computer Journal on Kolmogorov Complexity (1999), DOI: 10.1093/comjnl/42.4.251 Tributes to, pictures of, bibliography of, etc. Andrei Nikolaevich Kolmogorov.

Go to theDictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 6 May 2019.
HTML page formatted Wed Oct 30 12:15:30 2024.

Cite this as:
Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999, "Kolmogorov complexity", inDictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 6 May 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/kolmogorov.html