Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userKL-randomness and effective dimension under strong reducibility
184
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We show that the (truth-table) Medvedev degree KLR of Kolmogorov--Loveland randomness coincides with that of Martin Lof randomness, MLR, answering a question of Miyabe. Next, an analogue of complex packing dimension is studied which gives rise to a set of weak truth-table Medvedev degrees isomorphic to the Turing degrees.
rate research
Read More
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.
We investigate which infinite binary sequences (reals) are effectively random with respect to some continuous (i.e., non-atomic) probability measure. We prove that for every n, all but countably many reals are n-random for such a measure, where n indicates the arithmetical complexity of the Martin-Lof tests allowed. The proof is based on a Borel determinacy argument and presupposes the existence of infinitely many iterates of the power set of the natural numbers. In the second part of the paper we present a metamathematical analysis showing that this assumption is indeed necessary. More precisely, there exists a computable function G such that, for any n, the statement `All but countably many reals are G(n)-random with respect to a continuous probability measure cannot be proved in $ZFC^-_n$. Here $ZFC^-_n$ stands for Zermelo-Fraenkel set theory with the Axiom of Choice, where the Power Set Axiom is replaced by the existence of n-many iterates of the power set of the natural numbers. The proof of the latter fact rests on a very general obstruction to randomness, namely the presence of an internal definability structure.
In this paper, we study the power and limitations of computing effectively generic sequences using effectively random oracles. Previously, it was known that every 2-random sequence computes a 1-generic sequence (as shown by Kautz) and every 2-random sequence forms a minimal pair in the Turing degrees with every 2-generic sequence (as shown by Nies, Stephan, and Terwijn). We strengthen these results by showing that every Demuth random sequence computes a 1-generic sequence (which answers an open question posed by Barmpalias, Day, and Lewis) and that every Demuth random sequence forms a minimal pair with every pb-generic sequence (where pb-genericity is an effective notion of genericity that is strictly between 1-genericity and 2-genericity). Moreover, we prove that for every comeager $mathcal{G}subseteq 2^omega$, there is some weakly 2-random sequence $X$ that computes some $Yinmathcal{G}$, a result that allows us to provide a fairly complete classification as to how various notions of effective randomness interact in the Turing degrees with various notions of effective genericity.
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
