The Gateway to Computer Science Excellence
+37 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

in Theory of Computation by Veteran | 4.6k 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.

Is it correct thinking?

OPTION 1 : Since $L_1$ is enumerating all the strings over $\sum$ so for any $w_i$ and $w_j$ , strings of form $w_i \lt w_j$ would be accepted by the TM  and if it does not then it will be rejected by Turing machine which implies $L_2$ is recursive.

OPTION 2 : Strings in $L_2$ are enumerated using algorithm $A$ over $\sum$, hence all strings in $L_1$ are there in $L_2$.

Hence both $S1$ and $S2$ are true.
This problem reduces to

S1- Can L2 reduces to L1?

S2- Can L1 reduces to L2?

S1- for every wi#wj from L2, output wi and wj

S2 - for every 2 consecutive enumeration, make wi#wj

1 Answer

+38 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.

by Veteran
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.
Can anyone explain this line in detail
"to check if a word w belongs to L1, make a string w′=w1#w and give it to the decider for L2 and if accepted, then w belongs to L1 and not otherwise. " ??

Something related to this was asked in gate 2017 Set 1.

"Function f is computable iff"

In this question, can we use reducible concept?

What exactly this line means "An algorithm AA effectively enumerates its words as ω1,ω2,ω3,…."?

There is also the possibility that |Wi| = |Wj| as going by dictionary order allows j > i even if words are same size. Therefore this is not sufficient to ensure j > i. The only way is the manually enumerate using A and check.

Related questions

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
52,215 questions
60,006 answers
94,688 users