Layerwise computability and image randomness

DOI10.1007/s00224-017-9791-8zbMath1395.68159arXiv1607.04232OpenAlexW2962994751WikidataQ57349352 ScholiaQ57349352MaRDI QIDQ1694009

Alexander Shen, Mathieu Hoyrup, Laurent Bienvenu

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 information theory (Kolmogorov complexity, etc.) (68Q30) Algorithmic randomness and dimension (03D32)

Related Items (4)

The Intersection of Algorithmically Random Closed Sets and Effective Dimension ⋮ PERMUTATIONS OF THE INTEGERS INDUCE ONLY THE TRIVIAL AUTOMORPHISM OF THE TURING DEGREES ⋮ Schnorr randomness for noncomputable measures ⋮ The Kučera-Gács theorem revisited by Levin

Cites Work

• Unnamed Item
• Algorithmic randomness and monotone complexity on product space
• Martin-Löf randomness and Galton-Watson processes
• Energy randomness
• Algorithmic tests and randomness with respect to a class of measures
• Probabilistic Constructions of Computable Objects and a Computable Version of Lovász Local Lemma
• An Application of Martin-Löf Randomness to Effective Probability Theory
• Applications of Effective Probability Theory to Martin-Löf Randomness
• Algorithmic Randomness of Closed Sets
• 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
• Probabilistic Recursive Functions

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