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 Eric Allender. The Strange Link between Incompressibility and Complexity <7>REric Allender: The Strange Link between Incompressibility and Complexity < 7 > 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|