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

  • 1
    $\begingroup$ "matches either $w_i$ or $w_j$" -- for which $i$ resp. $j$? $\endgroup$ – Raphael Nov 26 '12 at 15:12
  • $\begingroup$ @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$. $\endgroup$ – Abhijith Madhav Nov 26 '12 at 16:03
  • $\begingroup$ 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!) $\endgroup$ – Raphael Nov 26 '12 at 17:26
  • 1
    $\begingroup$ 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. $\endgroup$ – Andrej Bauer Nov 27 '12 at 1:03
  • 1
    $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ Concerning statement 2: $w_1$ can be hard-coded, and then we can drop the assumption that $L_1$ is recursively enumerable. $\endgroup$ – Yuval Filmus Nov 26 '12 at 21:45
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael Nov 26 '12 at 22:04
  • $\begingroup$ 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. $\endgroup$ – Hendrik Jan Nov 27 '12 at 1:12
  • $\begingroup$ @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. $\endgroup$ – Raphael Nov 27 '12 at 8:27
  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – Raphael Nov 27 '12 at 9:30
  • $\begingroup$ 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 :) $\endgroup$ – Hendrik Jan Nov 27 '12 at 10:04
  • $\begingroup$ @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? $\endgroup$ – Abhijith Madhav Nov 27 '12 at 10:19
  • $\begingroup$ @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. $\endgroup$ – Abhijith Madhav Nov 27 '12 at 10:26
  • $\begingroup$ @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. $\endgroup$ – Raphael Nov 27 '12 at 11:36

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.