The interplay of classes of algorithmically random objects

DOI10.4115/JLA.2015.7.7MaRDI QIDQ3467669zbMATH OpenOpenAlexFDO

Authors Quinn Culver, Christopher P. Porter

Publication date 4 February 2016

Published in Journal of Logic and Analysis (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

algorithmic randomnesscomputable analysisrandom closed setsrandom functionsrandom measures

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Applications of computability and recursion theory (03D80) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: We study algorithmically random closed subsets of $2^{o}mega$, algorithmically random continuous functions from $2^{o}mega$ to $2^{o}mega$, and algorithmically random Borel probability measures on $2^{o}mega$, especially the interplay between these three classes of objects. Our main tools are preservation of randomness and its converse, the no randomness ex nihilo principle, which say together that given an almost-everywhere defined computable map between an effectively compact probability space and an effective Polish space, a real is Martin-L"of random for the pushforward measure if and only if its preimage is random with respect to the measure on the domain. These tools allow us to prove new facts, some of which answer previously open questions, and reprove some known results more simply. Our main results are the following. First we answer an open question of Barmapalias, Brodhead, Cenzer, Remmel, and Weber by showing that $mathcalXsubseteq{2}^{o}mega$ is a random closed set if and only if it is the set of zeros of a random continuous function on $2^{o}mega$. As a corollary we obtain the result that the collection of random continuous functions on $2^{o}mega$ is not closed under composition. Next, we construct a computable measure $Q$ on the space of measures on $2^{o}mega$ such that $mathcalXsubseteq{2}^{o}mega$ is a random closed set if and only if $mathcalX$ is the support of a $Q$-random measure. We also establish a correspondence between random closed sets and the random measures studied by Culver in previous work. Lastly, we study the ranges of random continuous functions, showing that the Lebesgue measure of the range of a random continuous function is always contained in $(0,1)$.

Recommendations

• Random Continuous Functions
• Algorithmic randomness of continuous functions
• Algorithmic randomness and capacity of closed sets
• Logical Approaches to Computational Barriers
• Martin-Löf randomness in spaces of closed sets

Cited in

(11)

• Layerwise computability and image randomness
• The random members of a \({\Pi }_{1}^{0}\) class
• When does randomness come from randomness?
• Algorithmic randomness and capacity of closed sets
• scientific article; zbMATH DE number 4138829 (Why is no real title available?)
• scientific article; zbMATH DE number 1543075 (Why is no real title available?)
• The Intersection of Algorithmically Random Closed Sets and Effective Dimension
• A quest for algorithmically random infinite structures. II
• Logical Approaches to Computational Barriers
• Algorithmic randomness of continuous functions
• Effectively closed sets of measures and randomness

This page was built for publication: The interplay of classes of algorithmically random objects

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