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 :
Autre publication
submitted. 2016
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 : jeudi 11 janvier 2018 - 06:27:05

Identifiants

  • HAL Id : lirmm-01486486, version 1
  • ARXIV : 1607.04232

Citation

Laurent Bienvenu, Mathieu Hoyrup, Alexander Shen. Layerwise computability and image randomness. submitted. 2016. 〈lirmm-01486486〉

Partager

Métriques

Consultations de la notice

150