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.
Domaines
Informatique [cs]Origine | Fichiers produits par l'(les) auteur(s) |
---|
Loading...