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

$L= \{\langle M\rangle \mid L(M)\text{ is infinite}\}$

  1. $L$ is RE but $L'$ is not RE
  2. Both $L$ and  $L'$ are RE
  3. $L$ is not RE but $L'$ is  RE
  4. Both $L$ and  $L'$ are not RE
asked in Theory of Computation by Boss (18.1k points)
edited by | 909 views

3 Answers

+8 votes
Best answer

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

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" cases of the problem. 

Now, given a non-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) = $\Sigma^*$ 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). 

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

Proving L' is not RE is easy. 
L' = {<M> | L(M) is finite}

L(M) is finite is a non-monotonic property of TM. Because we can take TM $T_{yes}$ with $L(T_{yes} ) = \phi$ and $T_{no}$ with $L(T_{no}) = \Sigma^*$. Here, $T_{yes}$ satisfies the property (of being finite) and $T_{no}$ does not satisfy the property and $L(T_{yes}) \subset L(T_{no})$, making this a non-monotonic property of TM. And hence this becomes not RE as per Rice's theorem second part.

So, both L and L' are not RE making (D) the correct answer.

answered by Boss (18.1k points)
edited by
is it a typo "given a halting problem (<H>, w), " in the 4th para ? should it be 'non-halting' ?
yes, corrected now.

@Arjun sir

L={⟨M⟩∣L(M) is infinite}

Here, there doesn't exist two TM's such that (Tyes)⊂(Tno).

Then why is it non-re?

L={ML(M) is infinite}

Rice's theorem part 2 is one-way like Pumping lemma. Part-1 is 2 way.

@Arjun Sir, Can you please explain me the meaning of highlighted text. Also what is the relation between |w| & k.

@Kiran Karwa

Rice's theorem-2 is sufficient condition but not necessary condition.
what if I try to reduct from Halting problem, instead of Not-halting problem?
How would be the procedure? I just don't understand why you moved in nonRE direction.

+1 vote

is the correct answer
answered by (83 points)
0 votes

OPtion D

We cannot have Tyes and Tno such that L(Tyes)⊂L(Tno).

Hence, this is not a non-monotonic property and Rice’s 2nd theorem is not applicable.

Still, L={M∣L(M) is infinite } is not Turing recognizable (not recursively enumerable)

answered by Loyal (8.8k points)
edited by
Someone please explain what excatly

"L={⟨M⟩∣L(M) is infinite}" mean?

It means the language accepted by the turing machine M, ( which is L(M) ), is infinite. ie, the language L(M) contains infinite strings

If we consider t​​​​​​yes= a​​​​​*  and  t​​​​​​no= ∑* where ∑={a,b}

Here we can apply rice second theorem rt??

Hence we can prove it to be non RE

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

38,017 questions
45,509 answers
48,739 users