Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I know that halting problem is Turing degree $0'$.

So, what degree would Co-RE complete problems be in?

And is there any problem we can formulate (<- this might be too general, but let us say in terms of writable problems) or think of that has Turing degree greater than $0'$ while not in Co-RE?

share|improve this question
1  
Assuming Co-RE means the compliment is RE, wouldn't the degree just be the set of compliments of sets/problems (you can turn a set into a problem via membership in the set, and vice-versa) in $0'$? –  Alex Becker May 21 '12 at 1:10
1  
$A \equiv_T \omega - A$ so this would just be $\emptyset'$. –  William May 21 '12 at 1:57

2 Answers 2

up vote 1 down vote accepted

Sure, anything which is $\Sigma_2^0$-complete (has degree $0''$) should suffice. For example, determining whether the set $\{x: \varphi_{n}(x)\text{ converges}\}$ is finite is $\Sigma_2^0$-complete and thus has degree greater than $0'$ and is not co-RE.

share|improve this answer

In terms of Turing Degrees, a set and its complement has the same Turing Degree. Therefore, any $\Sigma_1^0$ complete and $\Pi_1^0$ complete set has the same Turing Degree, $\emptyset'$.

One way of producing more complex sets in term of Turing Degrees are taking higher jumps. For example, $\emptyset'' \not\leq_T \emptyset'$ and $\emptyset''$ is not $\Sigma_1^0$ or $\Pi_1^0$.

Also to be clear, c.e. and co-c.e. are not degrees. They can either mean a set which is c.e. or co-c.e. or a degree containing such sets. There are even sets below $\emptyset'$ which are neither c.e. or co-c.e.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.