Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

A Simple Proof of Miller-Yu Theorem

Bienvenu L., Merkle W., Shen A.

Fundamenta Informaticae

2008

Vol. 83, nr 1-2

21-24

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]).