# Theory Of Computation - recognizable and decidable

How to prove that for any language $A$, if $A$ is recognizable and $A \leq_m A^\complement$, then $A$ is decidable.

I know this theorem - A language is decidable iff both it and its complement are recognizable

How to explain this?

• Surely you mean "if $A$ is recognizable and $A \leq_m \bar{A}$, then $A$ is decidable"?
– mrp
Feb 11 '15 at 17:48

Definition 1: We write $$A \leq_m B$$ if there is a computable function $$f$$ such that for every $$w$$, $$w \in A \iff f(w) \in B$$.
Theorem 1: If $$A \leq_m B$$ and $$B$$ is recognizable, then $$A$$ is recognizable.
Theorem 2: A language $$A$$ is decidable iff $$A$$ and $$\bar{A}$$ is recognizable.
Now assume that $$A$$ is recognizable and $$A \leq_m \bar{A}$$. Notice that from Definition 1, $$w \in A \iff f(w) \in \bar{A}$$ also implies that $$w \in \bar{A} \iff f(w) \in A$$, so $$\bar{A} \leq_m A$$. Then, from Theorem 1, we can conclude that $$\bar{A}$$ is recognizable, and therefore we get from Theorem 2 that $$A$$ is decidable.