Full entry |
PDF
(1.6 MB)
Feedback

Kolmogorov complexity; typical string; pseudorandom generator

References:

[1] Calude C.: **Theories of Computational Complexity**. North–Holland, Amsterdam 1988 MR 0919945 | Zbl 0633.03034

[2] Fine T. L.: **Theories of Probability – an Examination of Foundations**. Academic Press, New York 1973 MR 0433529 | Zbl 0275.60006

[3] Kolmogorov A. N.: **Three approaches to the quantitative definition of information**. Problems Inform. Transmission 1 (1965), 1, 1–7 MR 0184801

[4] Kramosil I., Šindelář J.: **A note on the law of iterated logarithm from the viewpoint of Kolmogorov program complexity**. Problems Control Inform. Theory 16 (1987), 6, 399–409 MR 0930650

[5] Kramosil I., Šindelář J.: **On pseudo-random sequences and their relation to a class of stochastical laws**. Kybernetika 28 (1991), 6, 383–391 MR 1197721

[6] Li M., Vitayi P.: **Introduction to Kolmogorov Complexity and its Applications**. Springer, New York 1997 MR 1438307

[7] Martin-Löf P.: **The definition of random sequences**. Inform. and Control 9 (1966), 602–619 DOI 10.1016/S0019-9958(66)80018-9 | MR 0223179

[8] Rogers H., Jr.: **Theory of Recursive Functions and Effective Computability**. McGraw–Hill, New York 1967 MR 0224462 | Zbl 0256.02015

[9] Šindelář J., Boček P.: **Kolmogorov complexity and probability measures**. Kybernetika 38 (2002), 729–745 MR 1954394