0
$\begingroup$

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?

  • 1
    $A \equiv_T \omega - A$ so this would just be $\emptyset'$.2012-05-21

2 Answers 2

1

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.

3

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.