[Solved]: Decidability of languages

ignougroup
Problem Detail: 

$L_1$ is a recursively enumerable language over some alphabet $Sigma$. An algorithm effectively enumerates its words as $w_1, w_2, …$.
$L_2$ is another language over $Sigma cup {#}$ as ${w_i#w_j : w_i, w_j in L_1, i < j}$
Consider the following assertions.

  1. $L_1$ is recursive implies $L_2$ is recursive
  2. $L_2$ is recursive implies $L_1$ is recursive

Which statements is/are true?

I reasoned both the statements to be true. Statement 1 is true. $L_1$ is recursive means it can lexicographically enumerate its strings. The membership question for $L_2$ can be easily settled using the decider and lexicographic enumerator of $L_1$. Statement 2 is true. The algorithm which decides $L_2$ can be modified to accept if the input string matches either $w_i$ or $w_j$. This settles the membership question for $L_1$. The given solution to this question however says that statement 2 is false. Could you let me know if my reasoning has gone wrong someplace?

Asked By : Abhijith Madhav

Answered By : Hendrik Jan

You seem to be right. But as Raphael says, be careful. Statement 1. Note that the $L_2$ is defined using the enumerating algorithm $cal E$ for $L_1$, not by $L_1$ itself. To decide whether $u#v in L_2$, decide whether both $u,v$ in $L$, and if confirmed run the enumerator $cal E$ and see whether $u$ is output before $v$. As we know both strings are in $L_1$ this will terminate. Statement 2. If $L_1$ is finite, it is recursive, so we assume $L_1$ is infinite. Run $cal E$ and wait for first word $w_1$. Now a decider for $L_2$ can be turned into one for $L_1$ as follows. To test $uin L_1$ first check whether $u=w_1$, and then check $w_1#u in L_2$. This is then equivalent to $uin L_1$ as we do not have to worry about the $i<j$ requirement, which is now true by construction. I am not even certain we need to know $w_1$ by running $cal E$: we only want to verify there exists a decider, not whether one can be effectively constructed. That seems impossible. (edit) Just to note that Raphael has posted a more explicit “implementation” of these suggestions, which avoids possible ambiguities.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6917  Ask a Question  Download Related Notes/Documents

Leave a Reply