The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
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 Σ∗......????
asked in Theory of Computation by (157 points) | 11 views

Please log in or register to answer this question.

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
47,928 questions
52,334 answers
67,807 users