Decidability of languages

Question

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

Answer 1

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.

Answer 2

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.