# What is true about the languages $L1$ and $L2$?

$L_1$ is a recursively enumerable language over $\Sigma$. An algorithm $A$ effectively enumerates its words as $\omega_1, \omega_2, \omega_3, \dots$

Define another language $L_2$ over $\Sigma \cup \left\{\text{#}\right\}$ as $$\left\{w_i \text{#} w_j \mid w_i, w_j \in L_1, i < j \right\}$$ Here # is new symbol. Now, Consider the following assertions.

• $S_1:L_1$ is recursive implies $L_2$ is recursive

• $S_2:L_2$ is recursive implies $L_1$ is recursive

Which of the above assertions can I say are true ?

## 1 Answer

if $L_1$ is finite, both $L_1$ and $L_2$ are recursive, so we suppose them infinite.

$S_1$ is true. Suppose $L_1$ is recursive, then there is a program $P_1$ from $\Sigma^*$ to $\{True,False\}$, such that $P_1(w)$ is true iff $w\in L_1$. Then you can easily define $$P_2(w_a\#w_b)=\mbox{if } P_1(w_a)\wedge P_2(w_b) \mbox{ then find if } a<b$$ Find $a<b$ means enumerating $L_1$ until you find $w_a$ (but return false if you find $w_b$ before). $P_2$ proves that $L_2$ is recursive because $w\in L_2$ iff $P_2(w)$ is true.

$S_2$ is true also. Now, $L_2$ is recursive, so you have $P_2$. There is a word $w'\in L_1$ so define $$P_1(w)=(w=w')\vee P_2(w\#w')\vee P_2(w'\#w)$$ showing that $L_1$ is recursive also.