Is Randomness native to Computer Science? Ten Years Later
Marie Ferbus-Zanda, Serge Grigorieff · 2012
2 What we have learned? A personal pick 4 2.1 From randomness to complexity . . . . . . . . . . . . . . . . . . . . . 4 2.2 Formalization of randomness: infinite strings . . . . . . . . . . . . . 5 2.3 Random versus lawless . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.4 Randomness and finite strings: incompressibility . . . . . . . . . . . 7 2.5 Representation and Kolmogorov complexity . . . . . . . . . . . . . . 8 2.6 Prefix-freeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.7 Approximating randomness and Kolmogorov complexity . . . . . . . 11