2
$\begingroup$

I found the following question with an answer here, but I can't understand the steps of the solution.

Show that if a language $A$ is in RE and $A \leq_m \overline{A}$, then $A$ is recursive.

Solution. Since $A \leq_m \overline{A}$, it follows that $\overline{A} \leq_m A$, and since $A$ is in RE, it follows that $\overline{A}$ is also in RE. Since both $A$ and $\overline{A}$ are in RE, it follows that $A$ is in R (this follows from a theorem you learned in class).

Here $\le_m$ demotes mapping reducibility.

Actually I can't understand most of the answer. In particular:

  1. Why does $A \leq_m \overline{A}$ imply $\overline{A} \leq_m A$?
  2. I understand the following step (why $\overline{A}$ is in RE).
  3. Which theorem is used to deduce that $A$ is in R? (I'm not a student in this class)
$\endgroup$
2
$\begingroup$
  1. It follows immediately from the definition of a mapping reduction that a reduction $f$ from $A$ to $B$ is also a reduction from $\overline{A}$ to $\overline{B}$. Indeed, if $f$ is a reduction from $A$ to $B$, then, in particular, $x\in A$ iff $f(x)\in B$, which is equivalent to $x\notin A$ iff $f(x)\notin B$, which is equivalent to $x\in \overline{A}$ iff $f(x) \in \overline{B}$. (I only used the fact that $x \to y$ is equivalent to $\neg y \to \neg x$).

  2. This follows form the reduction theorem: if $A \leq _m B$, then $B \in RE \to A\in RE$. Try to prove it. Hint: use a machine that computes the reduction, and a machine that recognizes $B$ in order to define a machine that recognizes $A$.

  3. To deduce that $A \in R$, they've used the fact that $R \supseteq RE\cap coRE$ (In fact, equality holds). Hint: If $M_{A}$ and $M_{\overline{A}}$ are machines that recognize $A$ and $\overline{A}$, respectively, then you know that for every word $w$, at least one of $M_{A}$ and $M_{\overline{A}}$ halts on $w$.

$\endgroup$
2
  • 2
    $\begingroup$ I think OP understands step 2. They don't understand step 3. $\endgroup$ – Yuval Filmus Jan 8 at 12:51
  • 1
    $\begingroup$ Thanks, I missed that. Editing the answer! $\endgroup$ – Bader Abu Radi Jan 8 at 12:52
2
$\begingroup$

The answer to the first question is quite simple. Suppose that $f$ is a mapping reduction from $A$ to $\overline{A}$. Then $f$ itself is also a mapping reduction from $\overline{A}$ to $A$. I'll let you verify that.

Next, let us show that if $A,\overline{A}$ are both RE, then $A$ is in R. How to show that depends on your definition of RE.

  • RE is the set of all languages which can be enumerated. Suppose that we can enumerate both $A$ and $\overline{A}$. Given a word $w$, here is how to decide whether $w \in A$ or not. Simply run both enumerators in parallel, until $w$ shows up. If it shows up in the enumeration of $A$, then $w \in A$, and if it shows up in the enumeration of $\overline{A}$, then $w \in \overline{A}$.

  • RE is the set of all recognizable languages, that is, there is a Turing machine which halts on an input iff it belongs to the language. Suppose that there are recognizers for both $A$ and $\overline{A}$. Given a word $w$, run both recognizers, until one of them halts. If the recognizer for $A$ halted, then $w \in A$, and if the recognizer for $\overline{A}$ halted, then $w \in \overline{A}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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