1
$\begingroup$

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

$\endgroup$
  • 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 '18 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 '18 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$ – ZeroDay Fracture Mar 31 '18 at 18:21
1
$\begingroup$

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.

$\endgroup$
  • $\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$ – ZeroDay Fracture Mar 31 '18 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$ – ZeroDay Fracture Mar 31 '18 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$ – ZeroDay Fracture Mar 31 '18 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 '18 at 21:54
  • $\begingroup$ ahhh I see I just have to check for instead of 1, ⊥ after finite |w| steps correct? $\endgroup$ – ZeroDay Fracture Mar 31 '18 at 21:55
1
$\begingroup$

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.

$\endgroup$
  • $\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$ – ZeroDay Fracture Mar 31 '18 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 '18 at 22:04

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.