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)?

  • 1
    $\begingroup$ 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. $\endgroup$
    – ttnick
    Mar 31, 2018 at 7:31
  • $\begingroup$ 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. $\endgroup$
    – Discrete lizard
    Mar 31, 2018 at 8:51
  • $\begingroup$ @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? $\endgroup$ Mar 31, 2018 at 18:21

2 Answers 2


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.

  • $\begingroup$ 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. $\endgroup$ Mar 31, 2018 at 21:41
  • $\begingroup$ wait why B={⟨x,w⟩∣MA(x)=1 after |w| steps} in |w| steps? do we need to dovetail? I don't think so? $\endgroup$ Mar 31, 2018 at 21:45
  • $\begingroup$ 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} $\endgroup$ Mar 31, 2018 at 21:47
  • $\begingroup$ 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. $\endgroup$
    – ttnick
    Mar 31, 2018 at 21:54
  • $\begingroup$ ahhh I see I just have to check for instead of 1, ⊥ after finite |w| steps correct? $\endgroup$ Mar 31, 2018 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.

  • $\begingroup$ 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. $\endgroup$ Mar 31, 2018 at 21:42
  • $\begingroup$ @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. $\endgroup$
    – chi
    Mar 31, 2018 at 22:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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