Strong reductions in effective randomness

DOI10.1016/J.TCS.2012.06.031MaRDI QIDQ1758164zbMATH OpenOpenAlexFDO

Authors Laurent Bienvenu, Christopher P. Porter

Publication date 8 November 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.06.031

zbMATH Keywords

computable analysisalgorithmic randomnessDemuth's theorem

Mathematics Subject Classification ID

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

Recommendations

• Reducibilities relating to Schnorr randomness
• Randomness and reducibility
• Measure-theoretic applications of higher Demuth's theorem
• On the interplay between effective notions of randomness and genericity
• scientific article; zbMATH DE number 1834658

Cites work

• scientific article; zbMATH DE number 4008384 (Why is no real title available?)
• scientific article; zbMATH DE number 4053595 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• Algorithmic randomness and complexity.
• Comparing notions of randomness
• Computability and Randomness
• Computable randomness and betting for computable probability spaces
• Constructive equivalence relations on computable probability measures
• General random sequences and learnable sequences
• Hyperimmune-free degrees and Schnorr triviality
• Kolmogorov-Loveland randomness and stochasticity
• Mathematical metaphysics of randomness
• Measures and their random reals
• Randomness, relativization and Turing degrees
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS

Cited in

(21)

• Computable randomness and betting for computable probability spaces
• Process and truth-table characterisations of randomness
• Microscopic reversibility and macroscopic irreversibility: from the viewpoint of algorithmic randomness
• Permutations of the integers induce only the trivial automorphism of the Turing degrees
• Demuth's path to randomness
• Algorithmically Random Functions and Effective Capacities
• When does randomness come from randomness?
• Schnorr randomness for noncomputable measures
• Demuth randomness and computational complexity
• Measure-theoretic applications of higher Demuth's theorem
• TT-functionals and Martin-Löf randomness for Bernoulli measures
• Rank and randomness
• Conditional measure and the violation of van Lambalgen's theorem for Martin-Löf randomness
• On effectively closed sets of effective strong measure zero
• Deep \(\Pi_1^0\) classes
• Strong Medvedev reducibilities and the KL-randomness problem
• Demuth's path to randomness
• Trivial measures are not so trivial
• Randomness for computable measures and initial segment complexity
• Effective randomness for continuous measures
• Partially effective randomization in simulations between ARBITRARY and COMMON PRAMs

This page was built for publication: Strong reductions in effective randomness

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