A mass problem is a set of Turing oracles. If P and Q are mass problems, we say that P is weakly reducible to Q if for all Y ∈ Q there exists X ∈ P such that X is Turing reducible to Y. A weak degree is an equivalence class of mass problems under mutual weak reducibility. Let [Formula: see text] be the lattice of weak degrees of mass problems associated with nonempty [Formula: see text] subsets of the Cantor (...) space. The lattice [Formula: see text] has been studied in previous publications. The purpose of this paper is to show that [Formula: see text] partakes of hyperarithmeticity. We exhibit a family of specific, natural degrees in [Formula: see text] which are indexed by the ordinal numbers less than [Formula: see text] and which correspond to the hyperarithmetical hierarchy. Namely, for each [Formula: see text], let hα be the weak degree of 0, the αth Turing jump of 0. If p is the weak degree of any mass problem P, let p* be the weak degree of the mass problem P* = {Y | ∃X ⊆ BLR )} where BLR is the set of functions which are boundedly limit recursive in X. Let 1 be the top degree in [Formula: see text]. We prove that all of the weak degrees [Formula: see text], [Formula: see text], are distinct and belong to [Formula: see text]. In addition, we prove that certain index sets associated with [Formula: see text] are [Formula: see text] complete. (shrink)

Direct download(3 more)   Export citation   Bookmark   16 citations  

We call A weakly low for K if there is a c such that $K^A(\sigma)\geq K(\sigma)-c$ for infinitely many σ; in other words, there are infinitely many strings that A does not help compress. We prove that A is weakly low for K if and only if Chaitin's Ω is A-random. This has consequences in the K-degrees and the low for K (i.e., low for random) degrees. Furthermore, we prove that the initial segment prefix-free complexity of 2-random reals is infinitely (...) often maximal. This had previously been proved for plain Kolmogorov complexity. (shrink)

Direct download(6 more)   Export citation   Bookmark   10 citations  

We say that A≤LRB if every B-random set is A-random with respect to Martin–Löf randomness. We study this relation and its interactions with Turing reducibility, classes, hyperimmunity and other recursion theoretic notions.

Direct download(4 more)   Export citation   Bookmark   10 citations  

Direct download(7 more)   Export citation   Bookmark   5 citations  

A set $B\subseteq\mathbb{N}$ is called low for Martin-Löf random if every Martin-Löf random set is also Martin-Löf random relative to B . We show that a $\Delta^0_2$ set B is low for Martin-Löf random if and only if the class of oracles which compress less efficiently than B , namely, the class $\mathcal{C}^B=\{A\ |\ \forall n\ K^B(n)\leq^+ K^A(n)\}$ is countable (where K denotes the prefix-free complexity and $\leq^+$ denotes inequality modulo a constant. It follows that $\Delta^0_2$ is the largest arithmetical (...) class with this property and if $\mathcal{C}^B$ is uncountable, it contains a perfect $\Pi^0_1$ set of reals. The proof introduces a new method for constructing nontrivial reals below a $\Delta^0_2$ set which is not low for Martin-Löf random. (shrink)

Direct download(6 more)   Export citation   Bookmark   5 citations  

Direct download(4 more)   Export citation   Bookmark   4 citations  

Given two infinite binary sequences A,B we say that B can compress at least as well as A if the prefix-free Kolmogorov complexity relative to B of any binary string is at most as much as the prefix-free Kolmogorov complexity relative to A, modulo a constant. This relation, introduced in Nies [14] and denoted by A≤LKB, is a measure of relative compressing power of oracles, in the same way that Turing reducibility is a measure of relative information. The equivalence classes (...) induced by ≤LK are called LK degrees and there is a least degree containing the oracles which can only compress as much as a computable oracle, also called the ‘low for K’ sets. A well-known result from Nies [14] states that these coincide with the K-trivial sets, which are the ones whose initial segments have minimal prefix-free Kolmogorov complexity. We show that with respect to ≤LK, given any non-trivial sets X,Y there is a computably enumerable set A which is not K-trivial and it is below X,Y. This shows that the local structures of and Turing degrees are not elementarily equivalent to the corresponding local structures in the LK degrees. It also shows that there is no pair of sets computable from the halting problem which forms a minimal pair in the LK degrees; this is sharp in terms of the jump, as it is known that there are sets computable from which form a minimal pair in the LK degrees. We also show that the structure of LK degrees below the LK degree of the halting problem is not elementarily equivalent to the or structures of LK degrees. The proofs introduce a new technique of permitting below a set that is not K-trivial, which is likely to have wider applications. (shrink)

Direct download(5 more)   Export citation   Bookmark   4 citations  

Direct download(5 more)   Export citation   Bookmark  

We survey recent advances on the interface between computability theory and algorithmic randomness, with special attention on measures of relative complexity. We focus on reducibilities that measure the initial segment complexity of reals and the power of reals to compress strings, when they are used as oracles. The results are put into context and several connections are made with various central issues in modern algorithmic randomness and computability.

Direct download(3 more)   Export citation   Bookmark   1 citation