Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPropagation of partial randomness
110
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let f be a computable function from finite sequences of 0s and 1s to real numbers. We prove that strong f-randomness implies strong f-randomness relative to a PA-degree. We also prove: if X is strongly f-random and Turing reducible to Y where Y is Martin-Lof random relative to Z, then X is strongly f-random relative to Z. In addition, we prove analogous propagation results for other notions of partial randomness, including non-K-triviality and autocomplexity. We prove that f-randomness relative to a PA-degree implies strong f-randomness, hence f-randomness does not imply f-randomness relative to a PA-degree.
rate research
Read More
We investigate the role of continuous reductions and continuous relativisation in the context of higher randomness. We define a higher analogue of Turing reducibility and show that it interacts well with higher randomness, for example with respect to van-Lambalgens theorem and the Miller-Yu / Levin theorem. We study lowness for continuous relativization of randomness, and show the equivalence of the higher analogues of the different characterisations of lowness for Martin-Lof randomness. We also characterise computing higher $K$-trivial sets by higher random sequences. We give a separation between higher notions of randomness, in particular between higher weak-2-randomness and $Pi^1_1$-randomness. To do so we investigate classes of functions computable from Kleenes~$O$ based on strong forms of the higher limit lemma.
We show that if a real $x$ is strongly Hausdorff $h$-random, where $h$ is a dimension function corresponding to a convex order, then it is also random for a continuous probability measure $mu$ such that the $mu$-measure of the basic open cylinders shrinks according to $h$. The proof uses a new method to construct measures, based on effective (partial) continuous transformations and a basis theorem for $Pi^0_1$-classes applied to closed sets of probability measures. We use the main result to give a new proof of Frostmans Lemma, to derive a collapse of randomness notions for Hausdorff measures, and to provide a characterization of effective Hausdorff dimension similar to Frostmans Theorem.
We study the question, ``For which reals $x$ does there exist a measure $mu$ such that $x$ is random relative to $mu$? We show that for every nonrecursive $x$, there is a measure which makes $x$ random without concentrating on $x$. We give several conditions on $x$ equivalent to there being continuous measure which makes $x$ random. We show that for all but countably many reals $x$ these conditions apply, so there is a continuous measure which makes $x$ random. There is a meta-mathematical aspect of this investigation. As one requires higher arithmetic levels in the degree of randomness, one must make use of more iterates of the power set of the continuum to show that for all but countably many $x$s there is a continuous $mu$ which makes $x$ random to that degree.
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-Lof 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.
We investigate the strength of a randomness notion $mathcal R$ as a set-existence principle in second-order arithmetic: for each $Z$ there is an $X$ that is $mathcal R$-random relative to $Z$. We show that the equivalence between $2$-randomness and being infinitely often $C$-incompressible is provable in $mathsf{RCA}_0$. We verify that $mathsf{RCA}_0$ proves the basic implications among randomness notions: $2$-random $Rightarrow$ weakly $2$-random $Rightarrow$ Martin-L{o}f random $Rightarrow$ computably random $Rightarrow$ Schnorr random. Also, over $mathsf{RCA}_0$ the existence of computable randoms is equivalent to the existence of Schnorr randoms. We show that the existence of balanced randoms is equivalent to the existence of Martin-L{o}f randoms, and we describe a sense in which this result is nearly optimal.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
