Layerwise Computability and Image Randomness

Laurent Bienvenu 1 Mathieu Hoyrup 2 Alexander Shen 1
1 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : Algorithmic randomness theory starts with a notion of an individual random object. To be reasonable, this notion should have some natural properties; in particular, an object should be random with respect to the image distribution F(P) (for some distribution P and some mapping F) if and only if it has a P-random F-preimage. This result (for computable distributions and mappings, and Martin-Löf randomness) was known for a long time (folklore); for layerwise computable mappings it was mentioned in Hoyrup and Rojas (2009, Proposition 5) (even for more general case of computable metric spaces). In this paper we provide a proof and discuss the related quantitative results and applications.
Type de document :
Article dans une revue
Theory of Computing Systems, Springer Verlag, 2017, 61 (4), pp.1353-1375. 〈10.1007/s00224-017-9791-8〉
Liste complète des métadonnées
Contributeur : Mathieu Hoyrup <>
Soumis le : mardi 28 novembre 2017 - 14:58:54
Dernière modification le : mardi 18 décembre 2018 - 16:48:02



Laurent Bienvenu, Mathieu Hoyrup, Alexander Shen. Layerwise Computability and Image Randomness. Theory of Computing Systems, Springer Verlag, 2017, 61 (4), pp.1353-1375. 〈10.1007/s00224-017-9791-8〉. 〈hal-01650910〉



Consultations de la notice