The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+20 votes

$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. 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 following statements is true?

  1. Both $S_1$ and $S_2$ are true

  2. $S_1$ is true but $S_2$ is not necessarily true

  3. $S_2$ is true but $S_1$ is not necessarily true

  4. Neither is necessarily true

asked in Theory of Computation by Veteran (69k points) | 2.1k views
Please explain
@Bikram sir m not getting this wht exactly we have to prove in this type of questions ?

@  set2018

Two language , L1 and L2 is given .

now we have to show that , among these 2 statements :

  1. If L1 is recursive L2 must also be recursive .
  2. If L2 is recursive then L1 must also be recursive .

which are correct statements.

1 Answer

+23 votes
Best answer
$S_1$ is TRUE.

If $L_1$ is recursive $L_2$ must also be recursive. Because to check if a word $w = w_i\#w_j$ belong to $L_2$, we can give $w_i$ and $w_j$ to the decider for $L_1$ and if both are accepted then $w$ belong to $L_1$ and not otherwise.

$S_2$ is TRUE.

With a decider for $L_2$ we can make a decider for $L_1$ as follows. Let $w_1$ be the first string enumerated by algorithm $A$ for $L_1$. Now, to check if a word $w$ belongs to $L_1$, make a string $w' = w_1\#w$ and give it to the decider for $L_2$ and if accepted, then $w$ belongs to $L_1$ and not otherwise.

So, answer must be A.

PS: For the second part, the given construction can fail if $L_1$ happens to be a finite language (more specifically if $L_1$ is empty). But all finite languages are anyway decidable.
answered by Veteran (346k points)
edited by
but how to check string w1 of language L1 , using decider of language L2 ?

@Arjun sir, Just one doubt here : )

In case of S2- 


L2 = {wi#wj ∣ wi,wj ∈ L1, i < j }

Do we need to check with $w_1$ only for all w.? Can it be $w_2$ for some w. When we have already enumerated $w_2$, just like $w_1$. 


We do not need to check with w1 only. But doing with w1 is easier to prove.

As you told we can have any $w_i$ with $i < j$ in the enumeration order. Here $w_1$ is the first string and hence it can be used with any other string. For $w_2$ we must exclude #w_1$ and so on.
make a string w′=w1#w and give it to the decider for L2

how does this make decide the w belongs to L1

For S1, to check if wi#wj belongs to L2, we can check wi and wj using L1 but how can we check that i<j?

@Arjun sir

For S1, to check if wi#wj belongs to L2, we can check wi and wj using L1 but how can we check that i<j?

One possibility :

An algorithm A effectively enumerates its words as ω1,ω2,ω3,….

So, we can just check in this enumeration that wi precedes wj.

Is this correct ?

@VS, for $S1$, to check if $i<j$ we can give both strings of $L2$, $wi$ and $wj$ to enumerator of $L1$, and if $wi$ halts first before $wj$ halts then we can say that $i<j$.

or as we know $L1$ is recursive we can enumerate the strings of $L1$ in lexicographic order and if $|wi|$<$|wj|$ then we can be sure that $i<j$

Hi @VS and @reena_kandari ji,

Your opinion looks OK. Method of dovetailing could also be used on both possibilities $w_i$#$w_j$ and $w_j$#$w_i$. Definitely one of them will be accepted by $L_2$. Accordingly it could be decided wether $i<j$ or vice-versa.

Can you explain what do yu mean by "decider of L1 in a bit detail"

I am getting so much confused.

@Chhotu dovetailing need not be used when we know that L1 is recursive when L1 is recursive we are sure that there exists an enumerator which enumerates the strings of L1 in lexicographic order dovetailing is when when L1 is RE then we have to dovetail all the strings as we the internal turing machine in the enumerator need not halt for all the strings if given in lexicographic order thanks for the wonderful hint @reena_kandari 


Sir for S2, can we apply this approach:

We can say that problem L1 can be reduced to problem L2 since if we can solve L2(i.e. if TM for L2 halts, then TM for L1 will also halt), then we can also solve L1. If a string is present in L2, then the strings will surely be present in L1 and so TM for L1 will halt. If a string is not present in L2, then TM for L1 will also halt specifying the strings are not in L1 too. As L2 is recursive, so TM for L2 wont loop forever for any input string and hence TM for L1 wont also loop forever when given the same input strings.Therefore, from reducibility theorem, as L2 is recursive, so L1 is also recursive.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,705 questions
40,252 answers
38,860 users