The Kolmogorov complexity of an object, such as a piece of text, is a measure of the computational resources needed to specify the object. ( a.k.a. For example, consider the following two strings of length 64, each containing only lowercase letters, numbers, and spaces: abababababababababababababababababababababababababababababababab 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf The first string has a short English-language description, namely "ab 32 times", which consists of 11 characters. The second one has no obvious simple description (using the same character set) other than writing down the string itself, which has 64 characters. The complexity of a string is the length of the string's shortest description in some fixed universal description language. Strings whose Kolmogorov complexity is
small relative to the string's size are not considered to be complex.
The notion of Kolmogorov complexity is considered surprisingly deep and can be used to state and prove impossibility results akin to Gödel's incompleteness theorem and Turing's halting problem.If a description of |