2
$\begingroup$

Is it true that if $$ A \equiv_m \bar{A} $$ then A is recursive?

I think it is true but I can't prove it.

Appreciate your help!

$\endgroup$

1 Answer 1

4
$\begingroup$

If $A$ is recursively enumerable then $\bar{A} \leq_m A$ iff $A$ is recursive. Because, if $A$ is recursively enumerable and $f$ is a recursive function witnessing $\bar{A} \leq_m A$, then $$ \bar{A} = \{x: f(x) \in A\}, $$ so $\bar{A}$ is also recursively enumerable and thus $A$ is recursive.

However, it is easy to see that for any set $A$ if $X = A \oplus \bar{A}$ then $X \equiv_m \bar{X}$. So in general, $X \equiv_m \bar{X}$ does not imply that $X$ is recursive.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .