GATE CS 2004 Q89 — Undecidability

To determine the truth value of the assertions, we analyze both directions:

Assertion $S_1$: $L_1$ is recursive $\implies L_2$ is recursive

To decide if a string $z \in L_2$:

1. Verify if $z$ is of the form $x \# y$ where $x, y \in \Sigma^*$. If not, reject.
2. Since $L_1$ is recursive, decide if $x \in L_1$ and $y \in L_1$. If either is not, reject.
3. Since both $x, y \in L_1$, run the enumerator $A$ until both $x$ and $y$ are printed. This is guaranteed to terminate in finite time.
4. If $x$ is printed before $y$ (i.e., $i < j$), accept; otherwise, reject.

Since this procedure always halts and gives the correct answer, $L_2$ is recursive. Thus, $S_1$ is true.

Assertion $S_2$: $L_2$ is recursive $\implies L_1$ is recursive

If $L_1$ is empty or contains only one string, it is finite and trivially recursive. Otherwise, we can run the enumerator $A$ to find the first generated string, say $w_1$. To decide if any string $x \in \Sigma^*$ is in $L_1$:

1. If $x = w_1$, accept.
2. Otherwise, query the decider of $L_2$ with the string $w_1 \# x$.
3. If $w_1 \# x \in L_2$, then $x \in L_1$ (accept). If $w_1 \# x \notin L_2$, then $x \notin L_1$ (reject), because if $x$ were in $L_1$ (and $x \neq w_1$), its index $j$ would be $> 1$, which would force $w_1 \# x \in L_2$.

Thus, $L_1$ is recursive. So, $S_2$ is true.