Full entry |
PDF
(1.8 MB)
Feedback

Kolmogorov complexity; probability measure; infinite oscillation

References:

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

[2] Chaitin G. J.: **On the length of programs for computing finite binary sequences**. J. Assoc. Comput. Mach. 13 (1966), 547–569 DOI 10.1145/321356.321363 | MR 0210520 | Zbl 0158.25301

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

[4] Katseff H. P.: **Complexity dips in infinite binary sequences**. Inform. and Control 38 (1978), 258–263 DOI 10.1016/S0019-9958(78)90062-1 | MR 0509552

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

[6] Kolmogorov A. N., Uspenskiǐ V. A.: **Algorithms and randomness (in Russian)**. Teor. Veryatnost. i Primenen. 32 (1987), 3, 425–455 MR 0914935

[7] 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

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

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

[10] 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

[11] Martin–Löf P.: **Complexity oscillations in infinite binary sequences**. Z. Wahrsch. Verw. Gebiete 19 (1971), 225–230 DOI 10.1007/BF00534110 | MR 0451322 | Zbl 0212.23103

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

[13] Solomonoff R. J.: **A formal theory of inductive inference**. Part I. Inform. and Control 7 (1964), 1–22 DOI 10.1016/S0019-9958(64)90223-2 | MR 0172744 | Zbl 0259.68038

[14] Vovk V. G.: **The law of of the iterated logarithm for sequences that are random in the sense of Kolmogorov or chaotic (in Russian)**. Teor. Veroyatnost. i Primenen. 32 (1978), 3, 456–468 MR 0914936