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


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.


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.