If $A$ is c.e.-complete then the join of $A$ and $A^c$ isn't c.e

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

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

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}}$$

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.