-2
$\begingroup$

Let $A\subseteq\{0, 1\}^∗$, and let $A^c = \{0, 1\}^∗ \setminus A$ be the complement of $A$. Prove: If A is $\le_m$-complete for CE, then $A$ join $A^c$ is neither c.e. nor co-c.e.

c.e --> Computably enumerable

The join of two languages $A, B \subseteq \{0, 1\}^∗$ is defined by: $\{x0 \mid x\in A\} \cup \{y1 \mid y \in B\}$.

$\endgroup$
3
  • $\begingroup$ what is m-complete here? $\endgroup$ – nir shahar Apr 3 at 11:29
  • $\begingroup$ Probably completeness with respect to computable many-one reductions. $\endgroup$ – Yuval Filmus Apr 3 at 12:18
  • $\begingroup$ Oh man...i figured this out before I saw these solutions. thanks anyway. $\endgroup$ – CODER1030 Apr 3 at 18:01
2
$\begingroup$

Let $B$ be $A$ join $A^c$, for the concept of join defined in your question. Consider the language $H = \{\langle T \rangle \, \mid \, \text{$T$ is a Turing Machine that halts on empty input}\}$.

Let $f$ be $m$-reduction from $H$ to $A$. Given word $w \in \{0,1\}^*$ (think of this word as a Turing Machine), $w \in H \iff f(w) \in A \iff f(w)0 \in B$. Similarly, $w \not\in H \iff f(w) \not\in A \iff f(w)1 \in B$.

Suppose towards a contradiction that $B \in \mathsf{CE}$. Construct a Turing machine $M^*$ that simulates, in parallel, two executions of a Turing Machine $M$ that recognizes $B$ until one of them halts and accepts. One execution of $M$ has input $f(w)0$ and the other has input $f(w)1$. If $M(f(w)0)$ halts and accepts then $M^*$ accepts. If $M(f(w)1)$ halts and accepts, then $M^*$ rejects.

Since $f(w)0 \in B \iff f(w)1 \not\in B$, at least one of $M(f(w)0)$ and $M(f(w)1)$ eventually halts and accepts. This shows that $M^*$ decides $H$ and provides the sought contradiction ($H$ is a well-known undecidable language).

Suppose towards a contradiction that $B \in \mathsf{\text{co-CE}}$. Construct a Turing machine $\overline{M}^*$ that simulates, in parallel, two executions of a Turing Machine $\overline{M}$ that recognizes $\overline{B}$ until one of them halts and accepts. One execution of $\overline{M}$ has input $f(w)0$ and the other has input $f(w)1$. If $\overline{M}(f(w)0)$ halts and accepts then $\overline{M}^*$ rejects. If $\overline{M}(f(w)1)$ halts and accepts, then $\overline{M}^*$ accepts.

Since $f(w)0 \in \overline{B} \iff f(w)1 \not\in \overline{B}$, at least one of $\overline{M}(f(w)0)$ and $\overline{M}(f(w)1)$ eventually halts and accepts. This shows that $\overline{M}^*$ decides $H$ and provides the sought contradiction.

Therefore we must have $B \not\in \mathsf{CE}$ and $B \not\in \mathsf{\text{co-CE}}$

$\endgroup$
1
$\begingroup$

Suppose, for example, that $A$ join $A^c$ is c.e. Since $A$ is c.e.-complete, $A$ join $A^c$ reduces to $A$. In particular, $A^c$ reduces to $A$. Show that this leads to a contradiction.

The proof that $A$ join $A^c$ isn't co-c.e. is similar.

$\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.