|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 5 van 16 gevonden artikelen
| Titel: |
A Simple Proof of Miller-Yu Theorem |
| Auteur: |
Bienvenu, Laurent Merkle, Wolfgang Shen, Alexander |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 83 (2008) nr. 1-2 pagina's 21-24 |
| Jaar: |
2008-05-27 |
| Inhoud: |
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]). |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 5 van 16 gevonden artikelen
| << vorige | volgende >> |