# prove A is co-re

Working on some cs theory and solving a problem on computationally [=recursively] enumerable languages:

A language $A\subseteq \{0,1\}^*$ is co-c.e. if and only if there is a decidable language $B\subseteq \{0,1\}^*$ such that, for all $x\in\{0,1\}^*$,

$x\in A \Leftrightarrow (\forall w\in \{0,1\}^*) \langle x,w\rangle\in B$

This is a two sided proof since it is "iff"

=> Since $B$ is decidable therefore there exists a TM call $M1$ s.t. it decides $B$ so we build a new machine as follows. $M2$ couples $M1$ s.t. it uses $M1$ as a witness to verify whether the given input tuple for some $w$ element of $\{0,1\}^\ast$: $\langle x,w\rangle$ is rejected if so accept else reject.

Now this side of the proof is trivial, but I feel like for the other side we are essentially trying to prove the halting problem?

<= There exists a TM $M1$ s.t. it computes comp($A$), now if we are enumerating for all $w$ in the tuple $\langle x,w\rangle$; since it is an infinite set there is no possible way to guarantee the constructed machine will halt or not. (Halting problem)?

• Hint: Do the proof for c.e. sets, i.e. $x \in A \iff \exists w \in \{0,1\}^\ast. \langle x, w \rangle \in B$. From that you obtain your theorem immediately. – ttnick Mar 31 '18 at 7:31
• It seems you've tried to edit your post while not being logged in. Be aware that if you do so, we must approve your edits. If you edit a post made while logged in, you can edit immediately. – Discrete lizard Mar 31 '18 at 8:51
• @PHPNick How so, that problem is trivial both sides as it is only there exists and not for all. since this is for all how do we enumerate <x,w> which is uncountably infinite and guarantee given machine halts? – ZeroDay Fracture Mar 31 '18 at 18:21

Before I actually start answering your question, I will prove the following (see my comment):

A language $A \subseteq \{0, 1\}^\ast$ is recursively enumerable iff there exists a recursive language $B \subseteq \{0, 1\}^\ast$ sucht that for all $x \in \{0, 1\}^\ast$: $$x \in A \iff \exists w \in \{0, 1\}^\ast. \langle x , w \rangle \in B.$$

For recursively enumerable (r.e / c.e.) I think the following definition is common:

A language $A \subseteq \{0,1 \}^\ast$ is recursively enumerable if there exists a Turing machine $M$ such that for all $x \in \{0, 1\}^\ast$: $$M( x) = \begin{cases}1, & x \in A\\ \bot, & \text{otherwise.}\end{cases}$$

only if: Let $M_A$ be this machine. Let $B = \{\langle x, w \rangle \mid M_A(x) = 1 \text{ after } |w| \text{ steps}\}$. $B$ is recursive as we only need to simulate $M_A$ for a finite number of steps to get an answer. $B$ has obviously the desired property.
if: Let $B \subseteq \{0, 1\}^\ast$ recursive such that $x \in A \iff \exists w \in \{0, 1\}^\ast. \langle x, w \rangle \in B$. Let $M_B$ the machine that decides $B$. We define $M_A$ as follows: For input $x \in \{0, 1\}^\ast$ simulate $M_B$ multiple (maybe infinite) times: In the $i$-th simulationon we use $\langle x, w_i \rangle$ as input, where $w_i$ is the $i$-th word in the canonical orderng of $\{0, 1\}^\ast$. If $M_B$ outputs $1$ in some round $i$, $M_A$ terminates with output $1$. Otherwise, $M_A$ will never stop simulating $M_B$ with new $w_i$s. Thus, $$M_A(x) = \begin{cases}1, & \exists w \in \{0, 1\}^\ast. \langle x, w \rangle \in B\\ \bot, & \text{otherwise}\end{cases} = \begin{cases}1, & x \in A\\ \bot, & \text{otherwise.}\end{cases}$$ Hence, $A$ is recursively enumerable.

Now to your question: It is simply negation the conditions: $A$ is co-recursively enumerable iff there exists $B'$ (which is the complement of the $B$ I used above) such that for all $x \in A$: $$x \in A \iff \forall w \in \{0, 1\}^\ast. \langle x, w \rangle \in B'.$$ You can probably find a more direct argument but following the same idea as me. This proof was just what I had in my head the whole time.

• right so when I did the (there exists) I defined a language B = { <x,episilon> | x element of A} and then the rest of the proof is trivial as A is c.e and we use that TM to verify x element of A and we are done. This is because this is a property of there exists. But since this problem asks us to prove (For All) we need to define an launguage s.t B={<x,w>| x element of A and for all w element of {0,1}kleene} and this for me seems like the halting problem. – ZeroDay Fracture Mar 31 '18 at 21:41
• wait why B={⟨x,w⟩∣MA(x)=1 after |w| steps} in |w| steps? do we need to dovetail? I don't think so? – ZeroDay Fracture Mar 31 '18 at 21:45
• I will need to sit on this for a while I think I am starting to get this. But stuck on when you say {simulate MB multiple (maybe infinite) times} – ZeroDay Fracture Mar 31 '18 at 21:47
• Do you got why this proof implies your statement? If yes, you probably might have to twist your head a bit to get this proof. – ttnick Mar 31 '18 at 21:54
• ahhh I see I just have to check for instead of 1, ⊥ after finite |w| steps correct? – ZeroDay Fracture Mar 31 '18 at 21:55

For $\Leftarrow$, we are given a TM $M$ which decides $B$. To prove that $A$ is co-ce we need to construct a TM $N$ which accepts the complement of $A$. Concretely, we can craft $N$ so that it diverges on each word of $A$, and accepts each word on its complement $\overline A$.

We make $N$ take its input $x$, and then try all the words $w$, checking whether $\langle x,w \rangle\in B$. We can do this $M$ decides $B$. As soon as we find some $w$ such that $\langle x,w \rangle\notin B$, we stop and accept. If we don't find any such $w$, we diverge.

So, $N$ indeed accepts the complement of $A$ ($L(N)=\overline A$), which is what we wanted.

• but what if N goes on forever, there is no guarantee that it will halt and accept right? since we need to enumerate all <x,w> and there is no guarantee the new TM N halts given this is an infinite set. – ZeroDay Fracture Mar 31 '18 at 21:42
• @ZeroDayFracture If $N$ goes on forever, this means that all $w$ satisfy that condition, and by hypothesis $x \in A$. So we do not accept, which is precisely what we need to do ($x$ being in $A$). Halting and accepting would be wrong, since we need to do that only on the complement of $A$! Instead, diverging on $A$ is OK, since we must not accept in that case. – chi Mar 31 '18 at 22:04