Search

Schnorr showed that a real Xis Martin-Löf random if and only if K(X↾n)⩾n−cfor some constant cand all n, where Kdenotes the prefix-free complexity function. Fortnow (unpublished) and Nies, Stephan and Terwijn [J. Symbolic Logic70(2005), 515–535] observed that the condition K(X↾n)⩾n−ccan be replaced with K(X↾rn)⩾rn−c, for any fixed increasing computable sequence (rn), in this characterization. The purpose of this note is to establish the following generalisation of this fact. We show that Xis Martin-Löf random if and only if ∃c∀nK(X↾rn)⩾rn−c, where (rn)is any fixed pointedly X-computablesequence, in the sense that rnis computable from Xin a self-delimiting way, so that at most the first rnbits of Xare queried in the computation of rn. On the other hand, we also show that there are reals Xwhich are very far from being Martin-Löf random, but for which there exists some X-computable sequence (rn)such that ∀nK(X↾rn)⩾rn.

AbstractThe K-trivial sets form an ideal in the Turing degrees, which is generated by its computably enumerable (c.e.) members and has an exact pair below the degree of the halting problem. The question of whether it has an exact pair in the c.e. degrees was first raised in [22, Question 4.2] and later in [25, Problem 5.5.8].We give a negative answer to this question. In fact, we show the following stronger statement in the c.e. degrees. There exists a K-trivial degree dsuch that for all degrees a, bwhich are not K-trivial and a > d, b > dthere exists a degree vwhich is not K-trivial and a > v, b > v. This work sheds light to the question of the definability of the K-trivial degrees in the c.e. degrees.

AbstractWe study inversions of the jump operator on classes, combined with certain basis theorems. These jump inversions have implications for the study of the jump operator on the random degrees—for various notions of randomness. For example, we characterize the jumps of the weakly 2-random sets which are not 2-random, and the jumps of the weakly 1-random relative to 0' sets which are not 2-random. Both of the classes coincide with the degrees above 0' which are not 0'-dominated. A further application is the complete solution of [24, Problem 3.6.9]: one direction of van Lambalgen's theorem holds for weak 2-randomness, while the other fails.Finally we discuss various techniques for coding information into incomplete randoms. Using these techniques we give a negative answer to [24, Problem 8.2.14]: not all weakly 2-random sets are array computable. In fact, given any oracle X, there is a weakly 2-random which is not array computable relative to X. This contrasts with the fact that all 2-random sets are array computable.

AbstractWe prove a number of results in effective randomness, using methods in which ?10classes play an essential role. The results proved include the fact that every PA Turing degree is the join of two random Turing degrees, and the existence of a minimal pair of LR degrees below the LR degree of the halting problem.

AbstractWe say that A=LRBif every B-random number is A-random. Intuitively this means that if oracle Acan identify some patterns on some real ?, oracle Bcan also find patterns on ?. In other words, Bis at least as good as Afor this purpose. We study the structure of the LRdegrees globally and locally (i.e., restricted to the computably enumerable degrees) and their relationship with the Turing degrees. Among other results we show that whenever ? is not GL2the LRdegree of ? bounds degrees (so that, in particular, there exist LRdegrees with uncountably many predecessors) and we give sample results which demonstrate how various techniques from the theory of the c.e. degrees can be used to prove results about the c.e. LRdegrees.

Abstract: We show that there exists an almost everywhere (a.e.) dominating computably enumerable (c.e.) degree which is half of a minimal pair. [Copyright &y& Elsevier]

Lipschitz continuity is used as a tool for analysing the relationship between incomputability and randomness. We present a simpler proof of one of the major results in this area – the theorem of Yu and Ding, which states that there exists no cl-complete c.e. real – and go on to consider the global theory. The existential theory of the cl degrees is decidable, but this does not follow immediately by the standard proof for classical structures, such as the Turing degrees, since the cl degrees are a structure without join. We go on to show that strictly below every random cl degree there is another random cl degree. Results regarding the phenomenon of quasi-maximality in the cl degrees are also presented.

Given a 0''-computable real x we are interested in the relative complexity of the sets Az = {i: zi < x} for possible computable sequences of rationals z = {zs} with limszs = x, with respect to a strong reducibility ≤ = r. It turns out that the r-degree structure of these sets (excluding the trivial, i.e. the finite and co-finite ones) is a substructure of the ≤ = r-degrees inside the Turing degree of x and it can be non-trivial. In fact, we construct a real x = limszs = limsws such that AzǁwttAw. Also, it can be trivial even for non-computable reals x: there is a non-computable c.e. real x such that for all sequences z with limszs = x the sets Az (if co-infinite) have the same m-degree. Assigning such a degree structure to each 0''-computable real we propose the study of the complexity of a single real by means of the complexity of the correspondent degree structure. The variety of these degree structures from real to real indicates that a fine classification of the 0''-computable reals may be possible in this way. Finally, we study the immunity properties of Az: we prove that it cannot be (co-)hyperhyperimmune but it is always bi-hyperimmune or (co-)hypersimple if x is non-computable. [Copyright &y& Elsevier]