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
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.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01650910
Contributor : Mathieu Hoyrup <>
Submitted on : Saturday, April 20, 2019 - 11:21:59 AM
Last modification on : Friday, March 13, 2020 - 5:36:05 PM

File

1607.04232.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

467

Files downloads

379