Do stronger definitions of randomness exist?

✍ Scribed by Bruno Durand; Vladimir Kanovei; Vladimir A. Uspensky; Nikolai Vereshchagin

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 122 KB
• Volume: 290
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00040-3

✦ Synopsis

In this paper, we investigate reÿned deÿnition of random sequences. Classical deÿnitions (Martin-L of tests of randomness, uncompressibility, unpredictability, or stochasticness) make use of the notion of algorithm. We present alternative deÿnitions based on set theory and explain why they depend on the model of ZFC that is considered. We also present a possible generalization of the deÿnition when small inÿnite regularities are allowed.