edited by
5,640 views
17 votes
17 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
edited by

4 Answers

Best answer
24 votes
24 votes

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 $\langle H \rangle$ 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 $(\langle H \rangle, 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 for w in say $k$ steps, any string with length greater than $|k|,$ would certainly be not in $L$ (as we are running for only $|x|$ steps for input $x),$ 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' = \{\langle M \rangle \mid 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.

http://gatecse.in/wiki/Rice%27s_Theorem_with_Examples

edited by
1 votes
1 votes

If M is any machine, which has infinite length string, then either the machine will  halt or not on acceptance or rejection. Hence this is the halting problem and its undecidable. Hence not recursive enumerable. So its complement is also not RE. Hence option D is correct

Also note that since language is infinite so no algo is defined for it. Hence by church-turing thesis there is no TM that accepts it. Thus no machine exists to accept it. Hence undecidable

0 votes
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)

edited by
0 votes
0 votes
It is NOT RE . .

We prove this by a reduction from HP. τ (hM, xi) = hM0 i. M0 on input w: it runs M on x for |w| steps; it rejects if M halts on x within |w| steps, and accepts otherwise.

We now prove the validity of the reduction:

∗ hM, xi ∈ HP ⇒ M does not halt on x ⇒ M0 accepts all strings ⇒ L(M0 ) is infinite ⇒ M0 ∈ L6.

∗ hM, xi ∈/ HP ⇒ M halts on x within k steps ⇒ M0 rejects all strings whose length is greater than or equal to k ⇒ L(M0 ) is finite ⇒ M0 ∈/ L6.

Related questions

17 votes
17 votes
2 answers
1
gatecse asked Aug 20, 2014
2,331 views
$L= \{\langle M \rangle\mid L(M) = \Sigma^*\} $A. $L$ is RE but $L'$ is not REB. Both $L$ and $L'$ are REC. $L$ is not RE but $L'$ is RED. Both $L$ and $L'$ are not RE...