Is there an incomplete Turing degree that is not r.e.?

187 Views Asked by At

$\exists A \in \mathcal{P}(\mathbb{N}). (A \lt_T 0' \land \neg \exists B \in \Sigma_1. A \equiv_T B)$?

In words: does there exist a subset of natural numbers that is Turing reducible to the halting set but is not Turing equivalent to any computably enumerable set?

1

There are 1 best solutions below

3
On BEST ANSWER

Yes, there are.

There is a result from (G. E. Sacks, 1964) : r.e degree are dense. That means that if $A$ and $B$ are r.e Turing degrees (Turing degree that contains an enumerable set) such that $A<_TB$, then there is a r.e Turing degree such that $A<_TC<_TB$.

But there is another result that shows there are minimal degree : some degree $A$ such that $0<A$ but there is not any $B$ such that $0<B<A$. Of course such $A$ could not be r.e by previous result.

An article A Minimal Partial Degree ≤ 0' by Leonard P. Sasso, Jr. (1973) explains how to build such a minimal degree under $0'$.