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 image distribution if and only if it has a random preimage. This result (for computable distributions and mappings, and Martin-Löf randomness) was known for a long time (folklore); in this paper we prove its natural generalization for layerwise computable mappings, and discuss the related quantitative results.
Type de document :
Article dans une revue
Theory of Computing Systems, Springer Verlag, 2017, 61 (4), pp.1315-1336. 〈https://link.springer.com/〉. 〈10.1007/s00224-017-9789-2〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01486486
Contributeur : Alexander Shen <>
Soumis le : jeudi 9 mars 2017 - 20:33:05
Dernière modification le : mardi 11 septembre 2018 - 14:54:01

Lien texte intégral

Identifiants

Citation

Laurent Bienvenu, Mathieu Hoyrup, Alexander Shen. Layerwise computability and image randomness. Theory of Computing Systems, Springer Verlag, 2017, 61 (4), pp.1315-1336. 〈https://link.springer.com/〉. 〈10.1007/s00224-017-9789-2〉. 〈lirmm-01486486〉

Partager

Métriques

Consultations de la notice

228