Do most strong definitions of randomness exist?

Bruno Durand (1) , Vladimir Kanovei (1) , Vladimir A. Uspensky (1) , Nikolai Vereshagin (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

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.

Mots clés: Logics; Randomness; Solovay Model

Mots clés: Logique; Modèle de Solovay; Suites Aléatoire

Domaines: Informatique [cs]

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⟩