Kolmogorov Complexity >C()=mind: U(d)=X U is a "universal Turing machine >K(x)= mind: U(d)=X U is a universal prefix-free Turing machine Important property Invariance: The choice of the universal Turing machine U is unimportant (up to an additive constant) x is random if o(x)≥|x,orK(x)≥冈 Eric Allender. The Strange Link between Incompressibility and ComplexityEric Allender: The Strange Link between Incompressibility and Complexity < 8 > Kolmogorov Complexity  C(x) = min{|d| : U(d) = x} – U is a “universal” Turing machine  K(x) = min{|d| : U(d) = x} – U is a “universal” prefix-free Turing machine  Important property – Invariance: The choice of the universal Turing machine U is unimportant (up to an additive constant).  x is random if C(x) ≥ |x|, or K(x) ≥ |x|