We study the complexity of generic reals for computable Mathias forcing in the context of computability theory. The n -generics and weak n -generics form a strict hierarchy under Turing reducibility, as in the case of Cohen forcing. We analyze the complexity of the Mathias forcing relation, and show that if G is any n -generic with n≥2n≥2 then it satisfies the jump property G≡TG′⊕∅G≡TG′⊕∅. We prove that every such G has generalized high Turing degree, and so cannot have even (...) Cohen 1-generic degree. On the other hand, we show that every Mathias n-generic real computes a Cohen n-generic real. (shrink)

We introduce several highness notions on degrees related to the problem of computing isomorphisms between structures, provided that isomorphisms exist. We consider variants along axes of uniformity, inclusion of negative information, and several other problems related to computing isomorphisms. These other problems include Scott analysis (in the form of back-and-forth relations), jump hierarchies, and computing descending sequences in linear orders.

We study the degrees of bi-hyperhyperimmune sets. Our main result characterizes these degrees as those that compute a function that is not dominated by any ∆02 function, and equivalently, those that compute a weak 2-generic. These characterizations imply that the collection of bi-hhi Turing degrees is closed upwards.

There has recently been work by multiple groups in extracting the properties associated with cardinal invariants of the continuum and translating these properties into similar analogous combinatorial properties of computational oracles. Each property yields a highness notion in the Turing degrees. In this paper we study the highness notions that result from the translation of the evasion number and its dual, the prediction number, as well as two versions of the rearrangement number. When translated appropriately, these yield four new highness (...) notions. We will define these new notions, show some of their basic properties and place them in the computability-theoretic version of Cichoń's diagram. (shrink)

We introduce a hierarchy of degree structures between the Medvedev and Muchnik lattices which allow varying amounts of nonuniformity. We use these structures to introduce the notion of the uniformity of a Muchnik reduction, which expresses how uniform a reduction is. We study this notion for several well-known reductions from algorithmic randomness. Furthermore, since our new structures are Brouwer algebras, we study their propositional theories. Finally, we study if our new structures are elementarily equivalent to each other.

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)

Several notions of computability-theoretic reducibility between [Formula: see text] principles have been studied. This paper contributes to the program of analyzing the behavior of versions of Ramsey’s Theorem and related principles under these notions. Among other results, we show that for each [Formula: see text], there is an instance of RT[Formula: see text] all of whose solutions have PA degree over [Formula: see text] and use this to show that König’s Lemma lies strictly between RT[Formula: see text] and RT[Formula: see (...) text] under one of these notions. We also answer two questions raised by Dorais, Dzhafarov, Hirst, Mileti, and Shafer on comparing versions of Ramsey’s Theorem and of the Thin Set Theorem with the same exponent but different numbers of colors. Still on the topic of the effect of the number of colors on the computable aspects of Ramsey-theoretic properties, we show that for each [Formula: see text], there is an [Formula: see text]-coloring [Formula: see text] of [Formula: see text] such that every [Formula: see text]-coloring of [Formula: see text] has an infinite homogeneous set that does not compute any infinite homogeneous set for [Formula: see text], and connect this result with the notion of infinite information reducibility introduced by Dzhafarov and Igusa. Next, we introduce and study a new notion that provides a uniform version of the idea of implication with respect to [Formula: see text]-models of RCA0, and related notions that allow us to count how many applications of a principle [Formula: see text] are needed to reduce another principle to [Formula: see text]. Finally, we fill in a gap in the proof of Theorem 12.2 in Cholak, Jockusch, and Slaman. (shrink)

In the early nineties of the previous century, leaf languages were introduced as a means for the uniform characterization of many complexity classes, mainly in the range between P and PSPACE . It was shown that the separability of two complexity classes can be reduced to a combinatorial property of the corresponding defining leaf languages. In the present paper, it is shown that every separation obtained in this way holds for every generic oracle in the sense of Blum and Impagliazzo. (...) We obtain several consequences of this result, regarding, e. g., universal oracles, simultaneous separations and type-2 complexity. (shrink)