Search

We study degree-theoretic properties of reals that are not random with respect to any continuous probability measure (NCR). To this end, we introduce a family of generalized Hausdorff measures based on the iterates of the "dissipation" function of a continuous measure and study the effective nullsets given by the corresponding Solovay tests. We introduce two constructions that preserve non-randomness with respect to a given continuous measure. This enables us to prove the existence of NCR reals in a number of Turing degrees. In particular, we show that every Δ 2 0 -degree contains an NCR element. [ABSTRACT FROM AUTHOR]

Recently, a connection has been established between two branches of computability theory, namely between algorithmic randomness and algorithmic learning theory. Learning-theoretical characterizations of several notions of randomness were discovered. We study such characterizations based on the asymptotic density of positive answers. In particular, this note provides a new learning-theoretic definition of weak 2-randomness, solving the problem posed by (Zaffora Blando, Rev. Symb. Log. 2019). The note also highlights the close connection between these characterizations and the problem of convergence on random sequences. [ABSTRACT FROM AUTHOR]

Numerous learning tasks can be described as the process of extrapolating patterns from observed data. One of the driving intuitions behind the theory of algorithmic randomness is that randomness amounts to the absence of any effectively detectable patterns: it is thus natural to regard randomness as antithetical to inductive learning. Osherson and Weinstein [11] draw upon the identification of randomness with unlearnability to introduce a learning-theoretic framework (in the spirit of formal learning theory) for modelling algorithmic randomness. They define two success criteria—specifying under what conditions a pattern may be said to have been detected by a computable learning function—and prove that the collections of data sequences on which these criteria cannot be satisfied correspond to the set of weak 1-randoms and the set of weak 2-randoms, respectively. This learning-theoretic approach affords an intuitive perspective on algorithmic randomness, and it invites the question of whether restricting attention to learning-theoretic success criteria comes at an expressivity cost. In other words, is the framework expressive enough to capture most core algorithmic randomness notions and, in particular, Martin-Löf randomness—arguably, the most prominent algorithmic randomness notion in the literature? In this article, we answer the latter question in the affirmative by providing a learning-theoretic characterisation of Martin-Löf randomness. We then show that Schnorr randomness, another central algorithmic randomness notion, also admits a learning-theoretic characterisation in this setting. [ABSTRACT FROM AUTHOR]

We investigate the strength of a randomness notion ${\cal R}$ as a set-existence principle in second-order arithmetic: for each Z there is an X that is ${\cal R}$ -random relative to Z. We show that the equivalence between 2-randomness and being infinitely often C -incompressible is provable in $RC{A_0}$. We verify that $RC{A_0}$ proves the basic implications among randomness notions: 2-random $\Rightarrow$ weakly 2-random $\Rightarrow$ Martin-Löf random $\Rightarrow$ computably random $\Rightarrow$ Schnorr random. Also, over $RC{A_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öf randoms, and we describe a sense in which this result is nearly optimal. [ABSTRACT FROM AUTHOR]

We show that for each computable ordinal $\alpha > 0$ it is possible to find in each Martin-Löf random ${\rm{\Delta }}_2^0 $ degree a sequence R of Cantor-Bendixson rank α , while ensuring that the sequences that inductively witness R 's rank are all Martin-Löf random with respect to a single countably supported and computable measure. This is a strengthening for random degrees of a recent result of Downey, Wu, and Yang, and can be understood as a randomized version of it. [ABSTRACT FROM AUTHOR]

The article discusses randomness via infinite computation and effective descriptive set theory. It discusses a study on randomness beyond Π11-randomness and its Martin-Löf type variant. It focuses on a class strictly between Π1 1 and Σ1 2 that is given by the infinite time Turing machines (ITTMs). Results include mutual randoms not sharing information and that a version of van Lambalgen's theorem holds, and an analogue to a theorem of Sacks.

We call a subset of an ordinal λ recognizable if it is the unique subset x of λ for which some Turing machine with ordinal time and tape and an ordinal parameter, that halts for all subsets of λ as input, halts with the final state 0. Equivalently, such a set is the unique subset x which satisfies a given Σ 1 formula in L [ x ] . We further define the recognizable closure for subsets of λ by closing under relative recognizability for subsets of λ . We prove several results about recognizable sets and their variants for other types of machines. Notably, we show the following results from large cardinals. • Recognizable sets of ordinals appear in the hierarchy of inner models at least up to the level Woodin cardinals, while computable sets are elements of L. • A subset of a countable ordinal λ is in the recognizable closure for subsets of countable ordinals if and only if it is an element of the inner model M ∞ , which is obtained by iterating the least measure of the least fine structural inner model M 1 with a Woodin cardinal through the ordinals. [ABSTRACT FROM AUTHOR]

We give solutions to two of the questions in a paper by Brendle, Brooke-Taylor, Ng and Nies. Our examples derive from a 2014 construction by Khan and Miller as well as new direct constructions using martingales. At the same time, we introduce the concept of i.o. subuniformity and relate this concept to recursive measure theory. We prove that there are classes closed downwards under Turing reducibility that have recursive measure zero and that are not i.o. subuniform. This shows that there are examples of classes that cannot be covered with methods other than probabilistic ones. It is easily seen that every set of hyperimmune degree can cover the recursive sets. We prove that there are both examples of hyperimmune-free degree that can and that cannot compute such a cover. [ABSTRACT FROM AUTHOR]

A coarse description of a set A ⊆ ω is a set D ⊆ ω such that the symmetric difference of A and D has asymptotic density 0. We study the extent to which noncomputable information can be effectively recovered from all coarse descriptions of a given set A, especially when A is effectively random in some sense. We show that if A is 1-random and B is computable from every coarse description D of A, then B is K-trivial, which implies that if A is in fact weakly 2-random then B is computable. Our main tool is a kind of compactness theorem for cone-avoiding descriptions, which also allows us to prove the same result for 1-genericity in place of weak 2-randomness. In the other direction, we show that if $A \le _{{\rm{T}}} \emptyset {\rm{'}}$ is a 1-random set, then there is a noncomputable c.e. set computable from every coarse description of A, but that not all K-trivial sets are computable from every coarse description of some 1-random set. We study both uniform and nonuniform notions of coarse reducibility. A set Y is uniformly coarsely reducible to X if there is a Turing functional Φ such that if D is a coarse description of X, then ΦD is a coarse description of Y. A set B is nonuniformly coarsely reducible to A if every coarse description of A computes a coarse description of B. We show that a certain natural embedding of the Turing degrees into the coarse degrees (both uniform and nonuniform) is not surjective. We also show that if two sets are mutually weakly 3-random, then their coarse degrees form a minimal pair, in both the uniform and nonuniform cases, but that the same is not true of every pair of relatively 2-random sets, at least in the nonuniform coarse degrees. [ABSTRACT FROM PUBLISHER]

Analyzing the effective content of the Lebesgue density theorem played a crucial role in some recent developments in algorithmic randomness, namely, the solutions of the ML-covering and ML-cupping problems. Two new classes of reals emerged from this inquiry: the positive density points with respect to effectively closed (or $\prod _1^0$) sets of reals, and a proper subclass, the density-one points. Bienvenu, Hölzl, Miller, and Nies have shown that the Martin-Löf random positive density points are exactly the ones that do not compute the halting problem. Treating this theorem as our starting point, we present several new results that shed light on how density, randomness, and computational strength interact. [ABSTRACT FROM PUBLISHER]

Let ${\cal S}$ be a Scott set, or even an ω-model of WWKL. Then for each A ε S, either there is X ε S that is weakly 2-random relative to A, or there is X ε S that is 1-generic relative to A. It follows that if A1,…,An ε S are noncomputable, there is X ε S such that each Ai is Turing incomparable with X, answering a question of Kučera and Slaman. More generally, any ∀∃ sentence in the language of partial orders that holds in ${\cal D}$ also holds in ${{\cal D}^{\cal S}}$ , where ${{\cal D}^{\cal S}}$ is the partial order of Turing degrees of elements of ${\cal S}$. [ABSTRACT FROM AUTHOR]

Consider a randomness notion $${\mathcal{C}}$$ . A uniform test in the sense of $${\mathcal{C}}$$ is a total computable procedure that each oracle X produces a test relative to X in the sense of $${\mathcal{C}}$$ . We say that a binary sequence Y is $${\mathcal{C}}$$ -random uniformly relative to X if Y passes all uniform $${\mathcal{C}}$$ tests relative to X. Suppose now we have a pair of randomness notions $${\mathcal{C}}$$ and $${\mathcal{D}}$$ where $${\mathcal{C} \subseteq \mathcal{D}}$$ , for instance Martin-Löf randomness and Schnorr randomness. Several authors have characterized classes of the form Low( $${\mathcal{C}, \mathcal{D}}$$ ) which consist of the oracles X that are so feeble that $${\mathcal{C} \subseteq \mathcal{D}^X}$$ . Our goal is to do the same when the randomness notion $${\mathcal{D}}$$ is relativized uniformly: denote by Low $${\star(\mathcal{C},\mathcal{D})}$$ the class of oracles X such that every $${\mathcal{C}}$$ -random is uniformly $${\mathcal{D}}$$ -random relative to X. (1) We show that $${X\in Low ^\star}$$ (MLR, SR) if and only if X is c.e. tt-traceable if and only if X is anticomplex if and only if X is Martin-Löf packing measure zero with respect to all computable dimension functions. (2) We also show that $${X\in Low^\star}$$ (SR, WR) if and only if X is computably i.o. tt-traceable if and only if X is not totally complex if and only if X is Schnorr Hausdorff measure zero with respect to all computable dimension functions. [ABSTRACT FROM AUTHOR]