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

D

is the correct answer

---

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

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

---

 

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

Semi decidability – For all inputs with answer “yes” if we can say “yes” then semi decidable.

Now, for the above language can we say “yes”?

As we need to check infinite number of strings thus the language is NOT semi decidable (NOT RE)

For L’ – We can apply non-monotonic property as the Lyes subset Lno (phi subset sigma*).

Therefore the language is NOT Turing Recognizable and hence NOT RE.

Conclusion – Both L and L’ are NOT RE.

---

Can anyone explain meaning of "the new TM say A, which on input x, just simulates H on w for |x| steps"?

Answer 2

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

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?