Randomness > Which of these sequences did I obtain by flipping a coin? 0101010101010101010101010101010 0110100111111100111000100101100 1101010001011100111111011001010 1=0.3183098861837906715377675267450 > How many bits of information does each of these sequences contain? Eric Allender. The Strange Link between Incompressibility and Complexity
Eric Allender: The Strange Link between Incompressibility and Complexity < 6 > Randomness Which of these sequences did I obtain by flipping a coin? 0101010101010101010101010101010 0110100111111100111000100101100 1101010001011100111111011001010 1/π =0.3183098861837906715377675267450 How many bits of information does each of these sequences contain?
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>R
Eric 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|
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 Complexity
Eric 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|
KC and randomness >K(x and C(x) are close C(x)≤K()≤C(x)+2log|x Two notions of randomness Rc={:C(x)≥|X} Rk={x:K(x)≥} >.. actually, infinitely many notions of randomness R UX: Cu(x)2(] Eric Allender. The Strange Link between Incompressibility and Complexity <9>R
Eric Allender: The Strange Link between Incompressibility and Complexity < 9 > K, C, and Randomness K(x) and C(x) are “close”: – C(x) ≤ K(x) ≤ C(x) + 2 log |x| Two notions of randomness: – RC = {x : C(x) ≥ |x|} – RK = {x : K(x) ≥ |x|} …actually, infinitely many notions of randomness: – RCU = {x : CU(x) ≥ |x|}
KC and randomness >K(x and C(x) are close C(x)≤K()≤C(x)+2log|x Two notions of randomness Rc={:C(x)≥|X} Rk={x:K(x)≥} >.. actually, infinitely many notions of randomness RCu=(X: Cu()=Xl),RKu=(x: Ku(x)2xlh Eric Allender. The Strange Link between Incompressibility and Complexity 10>R
Eric Allender: The Strange Link between Incompressibility and Complexity < 10 > K, C, and Randomness K(x) and C(x) are “close”: – C(x) ≤ K(x) ≤ C(x) + 2 log |x| Two notions of randomness: – RC = {x : C(x) ≥ |x|} – RK = {x : K(x) ≥ |x|} …actually, infinitely many notions of randomness: – RCU = {x : CU(x) ≥ |x|}, RKU = {x : KU(x) ≥ |x|}