A Simple Proof of Miller-Yu Theorem

• Autorzy: Bienvenu L. , Merkle W. , Shen A.
• Języki publikacji: EN

Abstrakty

EN

A few years ago a nice criterion of Martin-Löf randomness in terms of plain (neither prefix nor monotone) Kolmogorov complexity was found (among many other results, it is published in [5]). In fact Martin-Löf came rather close to the formulation of this criterion around 1970 (see [4] and [7], p. 98); a version of it that involves both plain and prefix complexity was proven by Gacs in 1980 ([2], remark after corollary 5.4 on p. 391). We provide a simple proof of this criterion that uses only elementary arguments very close to the original proof of Levin-Schnorr criterion of randomness (1973) in terms of monotone complexity ([3, 6]).

Słowa kluczowe

EN

Martin-Löf randomness; Kolmogorov complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 83, nr 1-2
• Strony: 21--24
• Opis fizyczny: bibliogr. 7 poz.

Twórcy

autor

Bienvenu L.

autor

Merkle W.

autor

Shen A.

• Laboratoire d'Informatique Fondamentale, CNRS & Universite de Provence, Marseille, France,

Bibliografia

• [1] Bienvenu, L., Merkle,W.: Reconciling data compression andKolmogorov complexity, International Colloquium on Automata, Languages and Programming (ICALP 2007), 4596, Springer, 2007.
• [2] Gacs,P.: Exactexpressionsfor some randomness tests, Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik, 26, 1980, 385-394.
• [3] Levin, L.: The concept of random sequence, Doklady Akademii Nauk SSSR, 212, 1973, 548-550.
• [4] Martin-L of,P.: Complexoscillationsin infinite binary sequences, Z. Wahrscheinlichkeittheorie verw. Geibi-ete, 19, 1971,225-230
• [5] Miller, J.,Yu, L.: On initial segment complexity and degrees of randomness, Transactions of the American Mathematical Society, to appear.
• [6] Schnorr, C: Process complexity and effective random tests,, Journal of Computer and System Sciences, 7, 1973, 376-388.
• [7] Zvonkin, A., Levin, L.: The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms, Russian Mathematical Surveys, 25(6), 1970, 83-124