Kolmogorov complexity in its plain form, denoted 
for a finite binary string 
relative to a fixed universal
Turing machine 
, is the length of the shortest program
that makes 
output 
and halt. Thus
 |
where 
ranges over halting programs and 
is the number of bits in 
. Kolmogorov complexity therefore formalizes the length of
the shortest effective description of an individual object.
The value depends on the choice of universal Turing machine, but only by an additive amount independent of 
. In particular, for two suitable universal
Turing machines 
and 
, there is a constant 
such that
 |
for every string 
. This invariance theorem makes asymptotic
statements about Kolmogorov complexity independent of the reference machine.
An 
-bit string always has Kolmogorov
complexity at most 
because a program can contain
the string literally. A string
whose Kolmogorov complexity is close to 
cannot be substantially compressed by any algorithm.
However, there is no algorithm that computes exact
Kolmogorov complexity for every string; this incomputability
is closely related to the halting problem.
Unlike Shannon entropy, Kolmogorov complexity is assigned to an individual string rather than to a probability distribution. It should not be confused with bit complexity, which measures the computational resources used by an algorithm. Closely related formulations were introduced independently by Solomonoff (1964), Kolmogorov (1965), and Chaitin (1966).
