(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
Special issue of the Computer Journal on Kolmogorov Complexity (1999). Tributes to, pictures of, bibliography of, etc. Andrei Nikolaevich Kolmogorov.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 7 February 2005.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999, "Kolmogorov complexity", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 7 February 2005. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/kolmogorov.html