L(M) is infinite

Question

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

• 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

Comments

i am getting NOT RE.. as we have check for infinite cases and which becomes difficult to check for each string in an infinite set...

Answer 1

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

Comments

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={⟨M⟩∣L(M) is infinite}

---

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

---

@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.

Thanks

---

if you try to reduce it from halting problem, you can not prove that the language is not even RE. You can just prove that it is non recursive.

---

According to the answer- We make a new TM say A, which on input x, just simulates H on w for |x| steps.

why only for |x| steps? what if the turing machine rejects and halts after |x| steps??

can anyone clear?

---

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) = Σ∗ 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).

Please someone make this part more clear....

---

I dont know how to explain it better in words. But I do understand it is not easy to get. First time trying to understand this indeed took me days. And even in a video or class this is not so easy to explain as it requires 2 levels of thinking - dream within a dream kind of thing. When we reach TOC during schedule will see if there is some better way to explain.

---

Sir is it that we r trying to give input x and if Turing machine H doesn't halt for any mod x steps we keep accepting x and the moment it halts for any mod x we reject. So eventually if H doesn't halt for w in any case the language accepted is infinite. In case if H halts on w for any mod x, we reject and since H halts for mod x, it will halt for mod x+1 and so on so language accepted will be finite if H halts on x.

---

No :O Actually in my explanation we are creating (reducing) a different language and its TM. So, we are having 3 TMs in total here. 

1. $M_1$ for $L(M_1)$ is infinite
2. $M_2$ for non-halting problem
3. $M_3$ for doing the reduction $(A$ in the explanation $).$

I guess in your understanding you are having only $2$ Turing machines. 

---

Sir the third turing machine A can be added after this. Is my intuition of the basic concept correct ?

---

No. See our aim is to solve non-halting problem using $M_1$ and Turing machine $A$ helps in that. You should think like this.

---

I understand that we r trying to reduce non halting problem into our problem and prove it non re. I just want a bit explanation on utility of mod x steps? Please sir if u can explain a bit.

---

Something was not correct in the answer- can you see now if you are getting why string length is used?

---

@Arjun sir, help would be appreciated.

Why conclude that the initial assumption that L is RE is wrong? Why not conclude that the assumption of N saying Yes when A is given as input, is wrong?

I get that L is not RE because if N accepts A, then L(A) = infinite, and thus "Yes" case of Non-Halting problem is solved - but what if N rejects A or loops forever on input A? 

Wouldn't that mean L(A) is finite and the "No" case of Non-Halting problem will be solved, which is nothing but the "Yes" case of Halting Problem and also consistent with our very initial assumption that L is RE?

Answer 2

D

is the correct answer

Answer 3

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)

Comments

Someone please explain what excatly

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

---

@parshu

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

Answer 4

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.

Comments

According to the answer- We make a new TM say A, which on input x, just simulates H on w for |x| steps.

why only for |w| steps? what if the turing machine rejects and halts after |w| steps??

can anyone clear?