Layerwise computability and image randomness

DOI10.1007/S00224-017-9791-8MaRDI QIDQ1694009zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Laurent Bienvenu, Mathieu Hoyrup, A. Shen

Publication date 1 February 2018

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1607.04232

zbMATH Keywords

algorithmic randomnessrandomness deficiencyrandom closed setsimage randomnesslayerwise computability

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

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"of 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.

Recommendations

• The interplay of classes of algorithmically random objects
• Algorithmic randomness of continuous functions
• When does randomness come from randomness?
• Random Continuous Functions
• An application of Martin-Löf randomness to effective probability theory

Cites work

• scientific article; zbMATH DE number 472936 (Why is no real title available?)
• Algorithmic Randomness of Closed Sets
• Algorithmic randomness and monotone complexity on product space
• Algorithmic tests and randomness with respect to a class of measures
• An application of Martin-Löf randomness to effective probability theory
• Applications of Effective Probability Theory to Martin-Löf Randomness
• Energy randomness
• Martin-Löf randomness and Galton-Watson processes
• Probabilistic Recursive Functions
• Probabilistic constructions of computable objects and a computable version of Lovász local lemma
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The definition of random sequences

Cited in

(5)

• How complex is a random picture?
• Permutations of the integers induce only the trivial automorphism of the Turing degrees
• The Kučera-Gács theorem revisited by Levin
• Schnorr randomness for noncomputable measures
• The Intersection of Algorithmically Random Closed Sets and Effective Dimension

This page was built for publication: Layerwise computability and image randomness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1694009)