Do most strong definitions of randomness exist?

Abstract : 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.
Document type :
Reports
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101832
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:07:31 AM
Last modification on : Wednesday, September 11, 2019 - 3:28:02 PM

File

RR1998-22.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101832, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

5

Files downloads

7