We define the bounded jump of $A$ by $A^{b}=\{x\in \omega \mid \exists i\leq x[\varphi_{i}\downarrow \wedge\Phi_{x}^{A\upharpoonright \!\!\!\upharpoonright \varphi_{i}}\downarrow ]\}$ and let $A^{nb}$ denote the $n$th bounded jump. We demonstrate several properties of the bounded jump, including the fact that it is strictly increasing and order-preserving on the bounded Turing degrees. We show that the bounded jump is related to the Ershov hierarchy. Indeed, for $n\geq2$ we have $X\leq_{bT}\emptyset ^{nb}\iff X$ is $\omega^{n}$-c.e. $\iff X\leq_{1}\emptyset ^{nb}$, (...) extending the classical result that $X\leq_{bT}\emptyset '\iff X$ is $\omega$-c.e. Finally, we prove that the analogue of Shoenfield inversion holds for the bounded jump on the bounded Turing degrees. That is, for every $X$ such that $\emptyset ^{b}\leq_{bT}X\leq_{bT}\emptyset ^{2b}$, there is a $Y\leq_{bT}\emptyset ^{b}$ such that $Y^{b}\equiv_{bT}X$. (shrink)

We study ideals in the computably enumerable Turing degrees, and their upper bounds. Every proper ideal in the c.e. Turing degrees has an incomplete upper bound. It follows that there is no prime ideal in the c.e. Turing degrees. This answers a question of Calhoun [2]. Every proper ideal in the c.e. Turing degrees has a low2 upper bound. Furthermore, the partial order of ideals under inclusion is dense.

Let I be a countable jump ideal in $\mathscr{D} = \langle \text{The Turing degrees}, \leq\rangle$ . The central theorem of this paper is: a is a uniform upper bound on I iff a computes the join of an I-exact pair whose double jump a (1) computes. We may replace "the join of an I-exact pair" in the above theorem by "a weak uniform upper bound on I". We also answer two minimality questions: the class of uniform upper bounds (...) on I never has a minimal member; if ∪ I = L α [ A] ∩ ω ω for α admissible or a limit of admissibles, the same holds for nice uniform upper bounds. The central technique used in proving these theorems consists in this: by trial and error construct a generic sequence approximating the desired object; simultaneously settle definitely on finite pieces of that object; make sure that the guessing settles down to the object determined by the limit of these finite pieces. (shrink)

Where AR is the set of arithmetic Turing degrees, 0 (ω ) is the least member of { $\mathbf{\alpha}^{(2)}|\mathbf{a}$ is an upper bound on AR}. This situation is quite different if we examine HYP, the set of hyperarithmetic degrees. We shall prove (Corollary 1) that there is an a, an upper bound on HYP, whose hyperjump is the degree of Kleene's O. This paper generalizes this example, using an iteration of the jump operation into the transfinite which (...) is based on results of Jensen and is detailed in [3] and [4]. In $\S1$ we review the basic definitions from [3] which are needed to state the general results. (shrink)

Let d be a Turing degree, R[d] and Q[d] denote respectively classes of recursively enumerable (r.e.) and all degrees in which d is relatively enumerable. We proved in Ishmukhametov [1999] that there is a degree d containing differences of r.e.sets (briefly, d.r.e.degree) such that R[d] possess a least elementm $>$ 0. Now we show the existence of a d.r.e. d such that R[d] has no a least element. We prove also that for any REA-degree d below 0 $'$ (...) the class Q[d] cannot have a least element and more generally is not bounded below by a non-zero degree, except in the trivial cases. (shrink)

We compare various notions of algorithmic randomness. First we consider relativized randomness. A set is n-random if it is Martin-Löf random relative to ∅. We show that a set is 2-random if and only if there is a constant c such that infinitely many initial segments x of the set are c-incompressible: C ≥ |x|-c. The ‘only if' direction was obtained independently by Joseph Miller. This characterization can be extended to the case of time-bounded C-complexity. Next we prove some (...) results on lowness. Among other things, we characterize the 2-random sets as those 1-random sets that are low for Chaitin's Ω. Also, 2-random sets form minimal pairs with 2-generic sets. The r.e. low for Ω sets coincide with the r.e. K-trivial ones. Finally we show that the notions of Martin-Löf randomness, recursive randomness, and Schnorr randomness can be separated in every high degree while the same notions coincide in every non-high degree. We make some remarks about hyperimmune-free and PA-complete degrees. (shrink)

A computably enumerable degree a is called nonbounding, if it bounds no minimal pair, and plus cupping, if every nonzero c.e. degree x below a is cuppable. Let NB and PC be the sets of all nonbounding and plus cupping c.e. degrees, respectively. Both NB and PC are well understood, but it has not been possible so far to distinguish between the two classes. In the present paper, we investigate the relationship between the classes NB and PC, and show (...) that there exists a minimal pair which join to a plus cupping degree, so that PC ⊈ NB. This gives a first known difference between NB and PC. (shrink)

We characterise explicitly the decidable predicates on integers of Infinite Time Turing machines, in terms of admissibility theory and the constructible hierarchy. We do this by pinning down ζ, the least ordinal not the length of any eventual output of an Infinite Time Turing machine (halting or otherwise); using this the Infinite Time Turing Degrees are considered, and it is shown how the jump operator coincides with the production of mastercodes for the constructible hierarchy; further that (...) the natural ordinals associated with the jump operator satisfy a Spector criterion, and correspond to the L ζ -stables. It also implies that the machines devised are "Σ 2 Complete" amongst all such other possible machines. It is shown that least upper bounds of an "eventual jump" hierarchy exist on an initial segment. (shrink)

We exhibit a structural difference between the truth-table degrees of the sets which are truth-table above 0′ and the PTIME-Turing degrees of all sets. Though the structures do not have the same isomorphism type, demonstrating this fact relies on developing their common theory.

We characterise explicitly the decidable predicates on integers of Infinite Time Turing machines, in terms of admissibility theory and the constructible hierarchy. We do this by pinning down $\zeta$, the least ordinal not the length of any eventual output of an Infinite Time Turing machine ; using this the Infinite Time Turing Degrees are considered, and it is shown how the jump operator coincides with the production of mastercodes for the constructible hierarchy; further that the natural (...) ordinals associated with the jump operator satisfy a Spector criterion, and correspond to the L$_\zeta$-stables. It also implies that the machines devised are "$\Sigma_2$ Complete" amongst all such other possible machines. It is shown that least upper bounds of an "eventual jump" hierarchy exist on an initial segment. (shrink)

Proof uses forcing on perfect trees for 2-quantifier sentences in the language of arithmetic. The result extends to exact pairs for the hyperarithmetic degrees.

We exhibit a structural difference between the truth-table degrees of the sets which are truth-table above 0′ and the PTIME-Turing degrees of all sets. Though the structures do not have the same isomorphism type, demonstrating this fact relies on developing their common theory.

We prove that every Turing degree a bounding some non-GL₂ degree is recursively enumerable in and above (r.e.a.) some 1-generic degree.

A Turing degree d is homogeneous bounding if every complete decidable (CD) theory has a d-decidable homogeneous model A, i.e., the elementary diagram De (A) has degree d. It follows from results of Macintyre and Marker that every PA degree (i.e., every degree of a complete extension of Peano Arithmetic) is homogeneous bounding. We prove that in fact a degree is homogeneous bounding if and only if it is a PA degree. We do this by showing that there is (...) a single CD theory T such that every homogeneous model of T has a PA degree. (shrink)

We show that the identity bounded Turing degrees of computably enumerable sets are not dense.

The computable Lipschitz reducibility was introduced by Downey, Hirschfeldt and LaForte under the name of strong weak truth-table reducibility [6]). This reducibility measures both the relative randomness and the relative computational power of real numbers. This paper proves that the computable Lipschitz degrees of computably enumerable sets are not dense. An immediate corollary is that the Solovay degrees of strongly c.e. reals are not dense. There are similarities to Barmpalias and Lewis’ proof that the identity bounded (...) class='Hi'>Turing degrees of c.e. sets are not dense [2]), however the problem for the computable Lipschitz degrees is more complex. (shrink)

We show that there is a low T-upper bound for the class of K-trivial sets, namely those which are weak from the point of view of algorithmic randomness. This result is a special case of a more general characterization of ideals in $\Delta _2^0 $ T-degrees for which there is a low T-upper bound.

Much previous study has been done on the degree spectra of prime models of a complete atomic decidable theory. Here we study the analogous questions for homogeneous models. We say a countable model A has a d-basis if the types realized in A are all computable and the Turing degree d can list $\Delta _{0}^{0}$ -indices for all types realized in A. We say A has a d-decidable copy if there exists a model B ≅ A such that the (...) elementary diagram of B is d-computable. Goncharov, Millar, and Peretyat'kin independently showed there exists a homogeneous A with a 0-basis but no decidable copy. We prove that any homogeneous A with a 0'-basis has a low decidable copy. This implies Csima's analogous result for prime models. In the case where all types of the theory T are computable and A is a homogeneous model with a 0-basis, we show A has copies decidable in every nonzero degree. A degree d is 0-homogeneous bounding if any automorphically nontrivial homogeneous A with a 0-basis has a d-decidable copy. We show that the nonlow₂ $\Delta _{2}^{0}$ degrees are 0-homogeneous bounding. (shrink)

We show that there are Π5 formulas in the language of the Turing degrees, [Formula: see text], with ≤, ∨ and ∧, that define the relations x″ ≤ y″, x″ = y″ and so {x ∈ L2 = x ≥ y|x″ = y″} in any jump ideal containing 0. There are also Σ6&Π6 and Π8 formulas that define the relations w = x″ and w = x', respectively, in any such ideal [Formula: see text]. In the language with (...) just ≤ the quantifier complexity of each of these definitions increases by one. For a lower bound on definability, we show that no Π2 or Σ2 formula in the language with just ≤ defines L2 or L2. Our arguments and constructions are purely degree theoretic without any appeals to absoluteness considerations, set theoretic methods or coding of models of arithmetic. As a corollary, we see that every automorphism of [Formula: see text] is fixed on every degree above 0″ and every relation on [Formula: see text] which is invariant under the double jump or under join with 0″ is definable over [Formula: see text] if and only if it is definable in second order arithmetic with set quantification ranging over sets whose degrees are in [Formula: see text]. (shrink)

We show that, in the partial ordering of the computably enumerable computable Lipschitz degrees, there is a degree a>0a>0 such that the class of the degrees which do not cup to a is not bounded by any degree less than a. Since Ambos-Spies [1] has shown that, in the partial ordering of the c.e. identity-bounded Turing degrees, for any degree a>0a>0 the degrees which do not cup to a are bounded by the (...) 1-shift a+1a+1 of a where a+1shrink)

We say that A ≤LR B if every B-random number is A-random. Intuitively this means that if oracle A can identify some patterns on some real γ. In other words. B is at least as good as A for this purpose. We study the structure of the LR degrees globally and locally (i.e., restricted to the computably enumberable degrees) and their relationship with the Turing degrees. Among other results we show that whenever α in not GL₂ (...) the LR degree of α bounds $2^{\aleph _{0}}$ degrees (so that, in particular, there exist LR degrees 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. LR degrees. (shrink)

The Kolmogorov complexity of a finite binary string is the length of the shortest description of the string. This gives rise to some ‘standard’ lowness notions for reals: A isK-trivial if its initial segments have the lowest possible complexity and A is low forKif using A as an oracle does not decrease the complexity of strings by more than a constant factor. We weaken these notions by requiring the defining inequalities to hold only up to all${\rm{\Delta }}_2^0$orders, and call the (...) new notions${\rm{\Delta }}_2^0$-bounded K-trivialand${\rm{\Delta }}_2^0$-bounded low for K. Several of the ‘nice’ properties ofK-triviality are lost with this weakening. For instance, the new weaker definitions both give uncountable set of reals. In this paper we show that the weaker definitions are no longer equivalent, and that the${\rm{\Delta }}_2^0$-boundedK-trivials are cofinal in the Turing degrees. We then compare them to other previously studied weakenings, namelyinfinitely-often K-trivialityandweak lowness for K. We show that${\rm{\Delta }}_2^0$-boundedK-trivial implies infinitely-oftenK-trivial, but no implication holds between${\rm{\Delta }}_2^0$-bounded low forKand weakly low forK. (shrink)

We study the classes of hypersimple and semicomputable sets as well as their intersection in the weak truth table degrees. We construct degrees that are not bounded by hypersimple degrees outside any non-trivial upper cone of Turing degrees and show that the hypersimple-free c.e. wtt degrees are downwards dense in the c.e. wtt degrees. We also show that there is no maximal (w.r.t. ≤wtt) hypersimple wtt degree. Moreover, we consider the sets that (...) are both hypersimple and semicomputable, characterize them as the (bi-infinite) c.e. cuts of computable orderings of ℕ of order type ω+ω* and study their wtt degrees. We show that there are hypersimple degrees that are not bounded by any hypersimple semicomputable degree, investigate relationships with the join and look for maximal and minimal elements of related classes. (shrink)

We study the relationship between effective domination properties and the bounded jump. We answer two open questions about the bounded jump: We prove that the analogue of Sacks jump inversion fails for the bounded jump and the wtt-reducibility. We prove that no c.e. bounded high set can be low by showing that they all have to be Turing complete. We characterize the class of c.e. bounded high sets as being those sets computing the Halting (...) problem via a reduction with use bounded by an ω-c.e. function. We define several notions of a c.e. set being effectively dominant, and show that together with the bounded high sets they form a proper hierarchy. (shrink)

We study connections between strong reducibilities and properties of computably enumerable sets such as simplicity. We say that a class of computably enumerable sets bounded iff there is an m-incomplete computably enumerable set A such that every set in is m-reducible to A. For example, we show that the class of effectively simple sets is bounded; but the class of maximal sets is not. Furthermore, the class of computably enumerable sets Turing reducible to a computably enumerable set (...) B is bounded iff B is low2. For r = bwtt,tt,wtt and T, there is a bounded class intersecting every computably enumerable r-degree; for r = c, d and p, no such class exists. (shrink)

It is well known that the structure of honest elementary degrees is a lattice with rather strong density properties. Let $\mbox{\bf a} \cup \mbox{\bf b}$ and $\mbox{\bf a} \cap \mbox{\bf b}$ denote respectively the join and the meet of the degrees $\mbox{\bf a}$ and $\mbox{\bf b}$ . This paper introduces a jump operator ( $\cdot'$ ) on the honest elementary degrees and defines canonical degrees $\mbox{\bf 0},\mbox{\bf 0}', \mbox{\bf 0}^{\prime \prime },\ldots$ and low and high (...) class='Hi'>degrees analogous to the corresponding concepts for the Turing degrees. Among others, the following results about the structure of the honest elementary degrees are shown: There exist low degrees, and there exist degrees which are neither low nor high. Every degree above $\mbox{\bf 0}'$ is the jump of some degree, moreover, for every degree $\mbox{\bf c}$ above $\mbox{\bf 0}'$ there exist degrees $\mbox{\bf a},\mbox{\bf b}$ such that $\mbox{\bf c}=\mbox{\bf a} \cup \mbox{\bf b} = \mbox{{\bf a}}'=\mbox{\bf b}'$ . We have $\mbox{\bf a}'\cup \mbox{\bf b}' \leq (\mbox{\bf a}\cup\mbox{\bf b})'$ and $\mbox{\bf a}'\cap \mbox{\bf b}' \geq (\mbox{\bf a}\cap \mbox{\bf b})'$ . The jump operator is of course monotonic, i.e. $\mbox{\bf a}\leq\mbox{{\bf b}}\Rightarrow \mbox{\bf a}'\leq \mbox{\bf b}'$ . We prove that every situation compatible with $\mbox{\bf a}\leq\mbox{\bf b}\Rightarrow \mbox{\bf a}'\leq \mbox{\bf b}'$ is realized in the structure, e.g. we have incomparable degrees $\mbox{\bf a},\mbox{\bf b}$ such that $\mbox{\bf a}'<\mbox{\bf b}'$ and incomparable degrees $\mbox{\bf a},\mbox{\bf b}$ such that $\mbox{\bf a}' = \mbox{\bf b}'$ etcetera. We are able to prove all these results without the traditional recursion theoretic constructions. Our proof method relies on the fact that the growth of the functions in a degree is bounded. This technique also yields a very simple proof of an old result, namely that the structure is a lattice. (shrink)

A mass problem is a set of functions $\omega \to \omega $. For mass problems ${\mathcal {C}}, {\mathcal {D}}$, one says that ${\mathcal {C}}$ is Muchnik reducible to ${\mathcal {D}}$ if each function in ${\mathcal {C}}$ is computed by a function in ${\mathcal {D}}$. In this paper we study some highness properties of Turing oracles, which we view as mass problems. We compare them with respect to Muchnik reducibility and its uniform strengthening, Medvedev reducibility.For $p \in [0,1]$ let ${\mathcal (...) {D}}$ be the mass problem of infinite bit sequences y such that for each computable bit sequence x, the bit sequence $ x {\,\leftrightarrow\,} y$ has asymptotic lower density at most p = y$ ). We show that all members of this family of mass problems parameterized by a real p with $0 p$ for each computable set x. We prove that the Medvedev complexity of the mass problems ${\mathcal {B}}$ is the same for all $p \in $, by showing that they are Medvedev equivalent to the mass problem of functions bounded by ${2^{2}}^{n}$ that are almost everywhere different from each computable function.Next, together with Joseph Miller, we obtain a proper hierarchy of the mass problems of type $\text {IOE}$ : we show that for any order function g there exists a faster growing order function $h $ such that $\text {IOE}$ is strictly above $\text {IOE}$ in the sense of Muchnik reducibility.We study cardinal characteristics in the sense of set theory that are analogous to the highness properties above. For instance, ${\mathfrak {d}} $ is the least size of a set G of bit sequences such that for each bit sequence x there is a bit sequence y in G so that $\underline \rho >p$. We prove within ZFC all the coincidences of cardinal characteristics that are the analogs of the results above. (shrink)

A uniform upper bound on a class of Turing degrees is the Turing degree of a function which parametrizes the collection of all functions whose degree is in the given class. I prove that if a is a uniform upper bound on an ideal of degrees then a is the jump of a degree c with this additional property: there is a uniform bound b<a so that b V c < a.

In this paper we consider the we known method by E. Post of solving the problem of construction of recursively enumerable sets that have a degree intermediate between the degrees of recursive and complete sets with respect to a given reducibility. Post considered reducibilities ≤m, ≤btt, ≤tt and ≤T and solved the problem for al of them except ≤T. Here we extend Post's original method of construction of incomplete sets onto two wide classes of sub-Turing reducibilities what were (...) studying in [1, 2]. (shrink)

We prove various results connected together by the common thread of computability theory.First, we investigate a new notion of algorithmic dimension, the inescapable dimension, which lies between the effective Hausdorff and packing dimensions. We also study its generalizations, obtaining an embedding of the Turing degrees into notions of dimension.We then investigate a new notion of computability theoretic immunity that arose in the course of the previous study, that of a set of natural numbers with no co-enumerable subsets. We (...) demonstrate how this notion of $\Pi ^0_1$ -immunity is connected to other immunity notions, and construct $\Pi ^0_1$ -immune reals throughout the high/low and Ershov hierarchies. We also study those degrees that cannot compute or cannot co-enumerate a $\Pi ^0_1$ -immune set.Finally, we discuss a recently discovered truth-table reduction for transforming a Kolmogorov–Loveland random input into a Martin-Löf random output by exploiting the fact that at least one half of such a KL-random is itself ML-random. We show that there is no better algorithm relying on this fact, in the sense that there is no positive, linear, or bounded truth-table reduction which does this. We also generalize these results to the problem of outputting randomness from infinitely many inputs, only some of which are random.Abstract prepared by David J. Webb.E-mail: [email protected]: https://arxiv.org/pdf/2209.05659.pdf. (shrink)

We study the jump hierarchy of d.c.e. Turing degrees and show that there exists a high d.c.e. degree d which does not bound any minimal pair of d.c.e. degrees.

The following theorems on the structure inside nonrecursive truth-table degrees are established: Dëgtev's result that the number of bounded truth-table degrees inside a truth-table degree is at least two is improved by showing that this number is infinite. There are even infinite chains and antichains of bounded truth-table degrees inside every truth-table degree. The latter implies an affirmative answer to the following question of Jockusch: does every truth-table degree contain an infinite antichain of many-one (...) class='Hi'>degrees? Some but not all truth-table degrees have a least bounded truth-table degree. The technique to construct such a degree is used to solve an open problem of Beigel, Gasarch and Owings: there are Turing degrees (constructed as hyperimmune-free truth-table degrees) which consist only of 2-subjective sets and therefore do not contain any objective set. Furthermore, a truth-table degree consisting of three positive degrees is constructed where one positive degree consists of enumerable semirecursive sets, one of coenumerable semirecursive sets and one of sets, which are neither enumerable nor coenumerable nor semirecursive. So Jockusch's result that there are at least three positive degrees inside a truth-table degree is optimal. The number of positive degrees inside a truth-table degree can also be some other odd integer as for example nineteen, but it is never an even finite number. (shrink)

The Sacks Density Theorem [7] states that the Turing degrees of the recursively enumerable sets are dense. We show that the Density Theorem holds in every model of P - + BΣ 2 . The proof has two components: a lemma that in any model of P - + BΣ 2 , if B is recursively enumerable and incomplete then IΣ 1 holds relative to B and an adaptation of Shore's [9] blocking technique in α-recursion theory to models (...) of arithmetic. (shrink)

We characterize the join-irreducible Medvedev degrees as the degrees of complements of Turing ideals, thereby solving a problem posed by Sorbi. We use this characterization to prove that there are Medvedev degrees above the second-least degree that do not bound any join-irreducible degrees above this second-least degree. This solves a problem posed by Sorbi and Terwijn. Finally, we prove that the filter generated by the degrees of closed sets is not prime. This solves a (...) problem posed by Bianchini and Sorbi. (shrink)

This paper continues our study of computable point-free topological spaces and the metamathematical points in them. For us, a point is the intersection of a sequence of basic open sets with compact and nested closures. We call such a sequence a sharp filter. A function fF from points to points is generated by a function F from basic open sets to basic open sets such that sharp filters map to sharp filters. We restrict our study to functions that have at (...) least all computable points in their domains.We follow Turing's approach in stating that a point is computable if it is the limit of a computable sharp filter; we then define the Turing degree Deg of a general point x in an analogous way. Because of the vagaries of the definition, a result of J. Miller applies and we note that not all points in all our spaces have Turing degrees; but we also show a certain class of points do. We further show that in ℝn all points have Turing degrees and that these degrees are the same as the classical Turing degrees of points defined by other researchers.We also prove the following: For a point x that has a Turing degree and lies either on a computable tree T or in the domain of a computable function fF, there is a sharp filter on T or in dom converging to x and with the same Turing degree as x. Furthermore, all possible Turing degrees occur among the degrees of such points for a given computable function fF or a complete, computable, binary tree T. For each x ∈ dom for which x and fF have Turing degrees, Deg) ≤ Deg. Finally, the Turing degrees of the sharp filters convergent to a given x are closed upward in the partial order of all Turing degrees. (shrink)

A model is computable if its domain is a computable set and its relations and functions are uniformly computable. Let be a computable model and let R be an extra relation on the domain of . That is, R is not named in the language of . We define to be the set of Turing degrees of the images f under all isomorphisms f from to computable models. We investigate conditions on and R which are sufficient and necessary (...) for to contain every Turing degree. These conditions imply that if every Turing degree 0″ can be realized in via an isomorphism of the same Turing degree as its image of R, then contains every Turing degree. We also discuss an example of and R whose coincides with the Turing degrees which are 0′. (shrink)

There is a Turing functional $\Phi $ taking $A^\prime $ to a theory $T_A$ whose complexity is exactly that of the jump of A, and which has the property that $A \leq _T B$ if and only if $T_A \trianglelefteq T_B$ in Keisler’s order. In fact, by more elaborate means and related theories, we may keep the complexity at the level of A without using the jump.

We give a partial answer to an important open problem in descriptive set theory, the Decomposability Conjecture for Borel functions on an analytic subset of a Polish space to a separable metrizable space. Our techniques employ deep results from effective descriptive set theory and recursion theory. In fact it is essential to extend several prominent results in recursion theory (e.g. the Shore-Slaman Join Theorem) to the setting of Polish spaces. As a by-product we give both positive and negative results on (...) the Martin Conjecture on the degree preserving Borel functions between Polish spaces. Additionally we prove results about the transfinite version as well as the computable version of the Decomposability Conjecture. (shrink)

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 (...) class='Hi'>Turing degrees. In particular, we show that every \(\Delta ^0_2\) -degree contains an NCR element. (shrink)

Martin [4, Theorems 1 and 2] proved that a Turing degree a is the degree of a maximal set if, and only if, a′ = 0″. Lachlan has shown that maximal sets have minimal many-one degrees [2, §1] and that every nonrecursive r.e. Turing degree contains a minimal many-one degree [2, Theorem 4]. Our aim here is to show that any r.e. Turing degree a of a maximal set contains an infinite number of maximal sets whose (...) many-one degrees are pairwise incomparable; hence such Turing degrees contain an infinite number of distinct minimal many-one degrees. This theorem has been proved by Yates [6, Theorem 5] in the case when a = 0′. The need for this theorem first came to our attention as a result of work done by the author [3, Theorem 2.3]. There we looked at the structure / obtained from the recursive functions of one variable under the equivalence relation f ~ g if, and only if, f(x) = g(x) a.e., that is, for all but finitely many x ∈, where M is a maximal set, and M is its complement. We showed that / 1 ≡ / 2 if, and only if, 1 = m 2, i.e., 1. and 2 have the same many-one degree. However, it might be possible that some Turing degree of a maximal set contains exactly one many-one degree of a maximal set. Theorem 1 was proved to show that this was not the case, and hence that the theory of / is not an invariant of Turing degree. (shrink)

Let be an infinite computable structure, and let R be an additional computable relation on its domain A. The syntactic notion of formal hypersimplicity of R on , first introduced and studied by Hird, is analogous to the computability-theoretic notion of hypersimplicity of R on A, given the definability of certain effective sequences of relations on A. Assuming that R is formally hypersimple on , we give general sufficient conditions for the existence of a computable isomorphic copy of on whose (...) domain the image of R is hypersimple and of arbitrary nonzero computably enumerable Turing degree. (shrink)

If X0and X1are both generic, the theories of the degrees below X0and X1are the same. The same is true if both are random. We show that then-genericity orn-randomness of X do not suffice to guarantee that the degrees below X have these common theories. We also show that these two theories are different. These results answer questions of Jockusch as well as Barmpalias, Day and Lewis.

We construct a recursive model , a recursive subset R of its domain, and a Turing degree x 0 satisfying the following condition. The nonrecursive images of R under all isomorphisms from to other recursive models are of Turing degree x and cannot be recursively enumerable.

It will be shown that there exist computably enumerable degrees a and b such that a $>$ b, and for any computably enumerable degree u, if u $\leq$ a and u is cappable, then u $<$ b.

In this paper, we prove that there exist computably enumerable degrees a and b such that $\mathbf{a} > \mathbf{b}$ and for any degree x, if x ≤ a and x is a minimal degree, then $\mathbf{x}.

Computably Lipschitz reducibility , was suggested as a measure of relative randomness. We say α≤clβ if α is Turing reducible to β with oracle use on x bounded by x+c. In this paper, we prove that for any non-computable real, there exists a c.e. real so that no c.e. real can cl-compute both of them. So every non-computable c.e. real is the half of a cl-maximal pair of c.e. reals.