A Simple Proof of Miller-Yu Theorem

Article type: Research Article

Authors: Bienvenu, Laurent | Merkle, Wolfgang | Shen, Alexander

Affiliations: Laboratoire d'Informatique Fondamentale, CNRS & Université de Provence, Marseille, France. E-mail: laurent.bienvenu@lif.univ-mrs.fr | Insitut für Informatik Ruprecht-Karls-Universität, Heidelberg, Germany. E-mail: merkle@math.uni-heidelberg.de | Laboratoire d'Informatique Fondamentale, CNRS & Université de Provence, Marseille, France Institute of Problems of Information Transmission, Moscow, Russia. E-mail: alexander.shen@lif.univ-mrs.fr

Abstract: 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 complexity1 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]).

Keywords: Martin-Löf randomness, Kolmogorov complexity

Journal: Fundamenta Informaticae, vol. 83, no. 1-2, pp. 21-24, 2008