Do most strong definitions of randomness exist? - LARA - Libre accès aux rapports scientifiques et techniques
Rapport (Rapport De Recherche) Année : 1998

Do most strong definitions of randomness exist?

Résumé

The goal of our paper is to propose a way to obtain more refined definitions of randomness than the notions known so far (e.g. Martin-Löf randomness). We show that a ``perfect'' definition of randomness based on provability does not exist. We then weaken our requirements on the definition by replacing provability by consistency and obtain a formula that defines a set of random sequences that fulfills rather strong conditions.
Nous proposons ici de raffiner les définitions classiques du caractère aléatoire des suites infinies (en particulier la très classique définition de Martin-Löf). Nous prouvons qu'il n'existe pas de définition parfaite fondée sur la notion de prouvabilité. En remplaçant la prouvabilité par la consistence, nous obtenons une définition des suites aléatoires très générale qui remplit des conditions raisonablement fortes.
Fichier principal
Vignette du fichier
RR1998-22.pdf (212.48 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02101832 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101832 , version 1

Citer

Bruno Durand, Vladimir Kanovei, Vladimir A. Uspensky, Nikolai Vereshagin. Do most strong definitions of randomness exist?. [Research Report] LIP RR-1998-22, Laboratoire de l'informatique du parallélisme. 1998, 2+11p. ⟨hal-02101832⟩
18 Consultations
23 Téléchargements

Partager

More