11 views
L={   ⟨M⟩ ∣L(M)=Σ∗  }

A. L is RE but L′ is not RE

B. Both L and  L′ are RE

C. L is not RE but L′ is  RE

D. Both L and  L′ are not RE

Yes. Both L and L' are not RE. We can have the same reduction as done for L(M) is infinite.

Lets assume L is RE. So, we have a TM N which will say "yes" if given an encoding of a TM whose language is Σ∗. Now using N we try to solve non-halting problem as follows:

Explanation :-
A non halting problem is given as follows: Given an encoding of TM <H> and a word w, whether H does not halt on w. That is, we have to decide if H does not halt on w. This problem is proved to be not RE and so no TM can not even say "yes" for "yes" case of the problem.

Now, given a halting problem (<H>, w), we proceed as follows: We make a new TM say A, which on input x, just simulates H on w for |x| steps. If H halts on w, A goes to reject state. Otherwise it accepts. So, L(A)=Σ∗  if H does not halt on w and L(A) = a finite set if H halts on w. (If H halts in |x| steps for w, any string with length greater than |w|, would certainly be not in L, making L a finite set and hence can never equal Σ∗).

Now, we just give the encoding of A to our assumed TM N. If N says "accept", we have that L(A) is Σ∗ => H does not halt on w => we solved "yes" case of not halting problem, which is not possible. Hence, our initial assumption of L is RE is false. L is not RE.

In this explanation given if H doesn't halt on w ,L(A) = Σ∗
Sir can u explain if H is not halting how langauge of A is becoming Σ∗......????

1
+1 vote
2
+1 vote