# Decidability of languages

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

• "matches either $w_i$ or $w_j$" -- for which $i$ resp. $j$? – Raphael Nov 26 '12 at 15:12
• @Raphael, I mean to say that the algorithm which decides $L_2$ can be modified to accept if the input string matches the $w_i$ or $w_j$ of $w_i\#w_j$, the form of the string of $L_2$. – Abhijith Madhav Nov 26 '12 at 16:03
• But where does it get the $w_i\#w_j$? You can't just go looking for one, that would only give you enumerability, not decidability. (You have to be really precise here!) – Raphael Nov 26 '12 at 17:26
• You are not allowed to change the enumeration of $L_1$ in step 1, so your reasoning for step 1 is faulty when you switch from the enumeration $w_i$ to the lexicographic enumeration. – Andrej Bauer Nov 27 '12 at 1:03
• You are not allowed to do that. The statement of the problem gives you an algorithm for enumerating $L_1$ and you have to use that one in the definition of $L_2$. You misunderstand the problem statement. – Andrej Bauer Nov 27 '12 at 3:20

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 $u\in L_1$ first check whether $u=w_1$, and then check $w_1\#u \in L_2$. This is then equivalent to $u\in 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.

• Concerning statement 2: $w_1$ can be hard-coded, and then we can drop the assumption that $L_1$ is recursively enumerable. – Yuval Filmus Nov 26 '12 at 21:45
• Depends; we don't know that $\cal{E}$ does not repeat itself. If it does, $w_1\# w_1 \in L_2$ after all. We can not decide that $w_1$ is never repeated. Of course, there is always a non-repeating enumerator, but since $L_2$ specifically depends on $\cal{E}$ it is not fair to assume we a have one. – Raphael Nov 26 '12 at 22:04
• Here we never check $w_1\#w_1$ to avoid problems. Input $u$ is checked "manually" to $w_1$. Apart from that the formulation suggests enumeration without repetition, precisely because your comment. – Hendrik Jan Nov 27 '12 at 1:12
• @HendrikJan I explained why checking $u=w_1$ is not enough to reject the $u$ in general. The formulation does not suggest enumeration without repetition; in fact, the OP says the given solution contradicts your answer, so that would point towards another interpretation. – Raphael Nov 27 '12 at 8:27
• I think I may have partially confused myself. I posted an answer myself, which I now think is equivalent to what you intended. In the process, I think I found a problem with our proof for the first statement. – Raphael Nov 27 '12 at 9:32

Ad 1: The statement is true, but your reasoning is not: you can not change the enumeration; the definition of $L_2$ is intimately tied to the order of elements. Here is the simple algorithm that decides $L_2$:

decide2(w) = {
(u,v) = split (w,#) // w = u#v

if ( decide1(u) && decide1(v) ) {
i = 1
while ( true ) {
if ( enumerate1(i) == u ) {
return true
}
else if ( enumerate1(i) == v ) {
return false
}
i += 1
}
}

return  false
}


Here, decide1 is the decider for $L_1$ and enumerate1 is the enumerator for $L_1$, which both exist by assumption. Note that the while loop always terminates; at that point, we know that $u,v \in L_1$ so the loop will find them (in fact, the one occurring first) eventually.

Ad 2: This statement is indeed true, but again for different reasons than you state.

If $L_2$ is recursive, the following program is computable and decides $L_1$:

decide1(w) = {
w1 = enumerate1(1)
if ( w == w1 ) }
return true
}
else {
return decider2(w1#w)
}
}


If $w = w_1$, we clearly have $w \in L_1$ and the program decides correctly. If $w \in L_1 \setminus \{w_1\}$, there is a $i > 1$ such that $w_i = w$, and therefore $w_1\#w \in L_2$; conversely, if $w \not\in L_1$, there is no such $i$ and thus $w_1\#w \not\in L_2$. The program decides correctly in all cases.

• Come to think of it, the first algorithm is flawed: if the enumeration has repetitions, we can not reject the input just because the first occurrences of $u,v$ are in the wrong order. – Raphael Nov 27 '12 at 9:30
• No hope for patching I tink. There is no way to decide whether there ever will be a second occurrence of the word $u$ (to check it occurs also after $v$). However the question said there were difficulties with Problem 2. Not Problem 1 :) – Hendrik Jan Nov 27 '12 at 10:04
• @Raphael, I don't understand what you mean by, "you can not change the enumeration". What enumeration have I changed? My reasoning for statement 1 being true is exactly what you have written in your answer above. After using the decider of $L_1$ to decide $u$ and $v$, you use the enumerator to check if $u$ is enumerated before $v$. Isn't this because you expect the enumerator of $L_1$ to lexicographically enumerate, now that the hypothesis of statement 1 says that $L_1$ is recursive? – Abhijith Madhav Nov 27 '12 at 10:19
• @Raphael, Your following comment has me more confused. Why do you now think that first occurrences of $u, v$ might be in the wrong order if the enumeration has repetitions. As $L_1$ is recursive, the enumeration cannot have $u, v$ in the wrong order. I just referenced a text book (sipser)to make sure that my "recursive implies lexicographically enumerable" is correct. – Abhijith Madhav Nov 27 '12 at 10:26
• @Abhijith From what you write in your question it is not clear exactly how you exploit that there is a lexicographic enumeration; you may not assume the enumeration defining $L_2$ is lexicographic, and it seems as if you did that. – Raphael Nov 27 '12 at 11:36