Search Results

Is there an r.e. set $A$ such that 0’ is cuppable relative to $A$? What about cappable? This is equivalent to asking if there is an r.e. $A$ such that 0’ is one half of a pair of $A$ r.e. non-$A$ co …

Just in case anyone else is a mere mortal and takes a moment to understand Slaman's answer here is a more spelled out version of his argument. I'll just do the capping side as it's the same argument …

So I'm looking at the proof of the ZBC lemma in Odifreddi's Classical Recursion Theory volume 2 page 808 and I don't see why $ 0' \oplus C$ produced computes $B'$ as claimed. The positive requirement …

I feel like there must be a classical result answering this question (or easily modified to do so) but a quick flip through Soare didn't produce anything so rather than waste time I figured I'd just a …

Is there a standard (or at least common) symbol in computability theory used to indicate that $x$ enters the c.e. set $W_e$ at stage $s$, i.e., $x \in W_{e,s} - W_{e,s-1}$ (at least for $s \neq 0$)? …

I’m mostly interested in this is the case where $A, \hat{A}$ are r.e. but the general case seems worth asking too. Suppose I have sets $A >_T \hat{A}$ with $A' \equiv_T \hat{A}'$. Does this imply tha …

The answer is no. Every properly n-REA set for n < 3 (I believe Peter Cholak and I have shown this fails at 3 but could always fall apart in write-up) can be extended to a properly n+1 REA set by add …

Remember, that an incomplete r.e. set $A$ is cuppable if there is an incomplete r.e. set $B$ such that $A\oplus B \equiv_T 0'$. It's relatively easy to build a low cuppable set but my question is whe …

In "A SPLITTING THEOREM FOR n−REA DEGREES" Shore and Slaman extend the following result of Sacks If $C$ is r.e., $D \leq_T C$ and $D, C \not\leq_T 0$ then there are sets $C_0, C_1$ such that $C \equ …

So a common method used to construct non-zero $\omega$-REA arithmetic degrees with various properties is to build an $\omega$-REA operator $J$ satisfying the constraints that (for all $X$) $$\tag{1} J …

So after some careful thought I'm pretty sure it is fully general. Let $A$ be a non-arithmetic $\omega$-REA set and $K(X)$ some $\omega$-REA operator satisfying 1 and 2 (see Odifreddi volume 2 XIII.3 …

Suppose that $A$ is an $\omega$-REA set (so $A^{[n]}$ is r.e. in the prior columns). It is a well-known result that if each column of $A$ is computable then $A \leq_T \emptyset^2$ ($\emptyset^2$ can …

Remember a degree $\mathbb{d}$ is the $n$-lub of $\mathbb{c}_j$ in the Turing degrees if it is the least element (not merely a minimal element) set of $\mathbb{c}^{(n)}$ such that $\mathbb{c}$ comput …

Ok, so unfortunately the answer is no. I've attached a proof that builds a $\omega$-REA set such that $A^{[\leq n]}$ is low for all $n$ yet $A$ computes $\emptyset'' \oplus X$ where $X$ is a natural …

Yes, it turns out that there is such an arithmetic (indeed 3-REA) non-trivial 2-lub. In fact, $\emptyset'''$ is such a degree. Consider the construction I give here in answer to this question. This …