HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

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
LORIA - FM - Department of Formal Methods , Inria Nancy - Grand Est
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.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

Contributor : Mathieu Hoyrup Connect in order to contact the contributor
Submitted on : Saturday, April 20, 2019 - 11:21:59 AM
Last modification on : Wednesday, November 3, 2021 - 8:05:54 AM


Files produced by the author(s)



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⟩



Record views


Files downloads