Schnorr randomness and computable randomness are natural concepts of random sequences. However van Lambalgen’s Theorem fails for both randomnesses. In this paper we define truth-table Schnorr randomness and truth-table reducible randomness, for which we prove that van Lambalgen's Theorem holds. We also show that the classes of truth-table Schnorr random reals relative to a high set contain reals Turing equivalent to the high set. It follows that each high Schnorr random real is half of a real for which van Lambalgen's (...) Theorem fails. Moreover we establish the coincidence between triviality and lowness notions for truth-table Schnorr randomness. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim. (shrink)

We show the existence of noncomputable oracles which are low for Demuth randomness, answering a question in [15] (also Problem 5.5.19 in [34]). We fully characterize lowness for Demuth randomness using an appropriate notion of traceability. Central to this characterization is a partial relativization of Demuth randomness, which may be more natural than the fully relativized version. We also show that an oracle is low for weak Demuth randomness if and only if it is computable.

Strong Turing Determinacy, or ${\mathrm {sTD}}$, is the statement that for every set A of reals, if $\forall x\exists y\geq _T x (y\in A)$, then there is a pointed set $P\subseteq A$. We prove the following consequences of Turing Determinacy ( ${\mathrm {TD}}$ ) and ${\mathrm {sTD}}$ over ${\mathrm {ZF}}$ —the Zermelo–Fraenkel axiomatic set theory without the Axiom of Choice: (1) ${\mathrm {ZF}}+{\mathrm {TD}}$ implies $\mathrm {wDC}_{\mathbb {R}}$ —a weaker version of $\mathrm {DC}_{\mathbb {R}}$.(2) ${\mathrm {ZF}}+{\mathrm {sTD}}$ implies that every (...) set of reals is measurable and has Baire property.(3) ${\mathrm {ZF}}+{\mathrm {sTD}}$ implies that every uncountable set of reals has a perfect subset.(4) ${\mathrm {ZF}}+{\mathrm {sTD}}$ implies that for every set of reals A and every $\epsilon>0$ :(a)There is a closed set $F\subseteq A$ such that $\mathrm {Dim_H}(F)\geq \mathrm {Dim_H}(A)-\epsilon $, where $\mathrm {Dim_H}$ is the Hausdorff dimension.(b)There is a closed set $F\subseteq A$ such that $\mathrm {Dim_P}(F)\geq \mathrm {Dim_P}(A)-\epsilon $, where $\mathrm {Dim_P}$ is the packing dimension. (shrink)

We call an $\alpha \in \mathbb {R}$ regainingly approximable if there exists a computable nondecreasing sequence $(a_n)_n$ of rational numbers converging to $\alpha $ with $\alpha - a_n n}$ for infinitely many n. Similarly, there exist regainingly approximable sets whose initial segment complexity infinitely often reaches the maximum possible for c.e. sets. Finally, there is a uniform algorithm splitting regular real numbers into two regainingly approximable numbers that are still regular.

In this survey we discuss work of Levin and V’yugin on collections of sequences that are non-negligible in the sense that they can be computed by a probabilistic algorithm with positive probability. More precisely, Levin and V’yugin introduced an ordering on collections of sequences that are closed under Turing equivalence. Roughly speaking, given two such collections $\mathcal {A}$ and $\mathcal {B}$, $\mathcal {A}$ is below $\mathcal {B}$ in this ordering if $\mathcal {A}\setminus \mathcal {B}$ is negligible. The degree structure associated (...) with this ordering, the Levin–V’yugin degrees, can be shown to be a Boolean algebra, and in fact a measure algebra. We demonstrate the interactions of this work with recent results in computability theory and algorithmic randomness: First, we recall the definition of the Levin–V’yugin algebra and identify connections between its properties and classical properties from computability theory. In particular, we apply results on the interactions between notions of randomness and Turing reducibility to establish new facts about specific LV-degrees, such as the LV-degree of the collection of 1-generic sequences, that of the collection of sequences of hyperimmune degree, and those collections corresponding to various notions of effective randomness. Next, we provide a detailed explanation of a complex technique developed by V’yugin that allows the construction of semi-measures into which computability-theoretic properties can be encoded. We provide two examples of the use of this technique by explicating a result of V’yugin’s about the LV-degree of the collection of Martin-Löf random sequences and extending the result to the LV-degree of the collection of sequences of DNC degree. (shrink)