Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the interplay between effective notions of randomness and genericity
136
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
We establish a framework for the study of the effective theory of weak convergence of measures. We define two effective notions of weak convergence of measures on $mathbb{R}$: one uniform and one non-uniform. We show that these notions are equivalent. By means of this equivalence, we prove an effective version of the Portmanteau Theorem, which consists of multiple equivalent definitions of weak convergence of measures.
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.
Quantum information processing shows advantages in many tasks, including quantum communication and computation, comparing to its classical counterpart. The essence of quantum processing lies on the fundamental difference between classical and quantum states. For a physical system, the coherent superposition on a computational basis is different from the statistical mixture of states in the same basis. Such coherent superposition endows the possibility of generating true random numbers, realizing parallel computing, and other classically impossible tasks such as quantum Bernoulli factory. Considering a system that consists of multiple parts, the coherent superposition that exists nonlocally on different systems is called entanglement. By properly manipulating entanglement, it is possible to realize computation and simulation tasks that are intractable with classical means. Investigating quantumness, coherent superposition, and entanglement can shed light on the original of quantum advantages and lead to the design of new quantum protocols. This thesis mainly focuses on the interplay between quantumness and two information tasks, randomness generation and selftesting quantum information processing. We discuss how quantumness can be used to generate randomness and show that randomness can in turn be used to quantify quantumness. In addition, we introduce the Bernoulli factory problem and present the quantum advantage with only coherence in both theory and experiment. Furthermore, we show a method to witness entanglement that is independent of the realization of the measurement. We also investigate randomness requirements in selftesting tasks and propose a random number generation scheme that is independent of the randomness source.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
