The Gateway to Computer Science Excellence

+11 votes

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

- $L$ is RE but $L'$ is not RE
- Both $L$ and $L'$ are RE
- $L$ is not RE but $L'$ is RE
- Both $L$ and $L'$ are not RE

+14 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 $\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

0

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

0

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

How would be the procedure? I just don't understand why you moved in nonRE direction.

Thanks

+1

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.

0

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?

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

can anyone clear?

0

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

Please someone make this part more clear....

0

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.

0

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.

0

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.

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

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

0

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

0

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.

0

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.

0

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

0

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

0 votes

O**Ption 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)

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.

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.

52,345 questions

60,510 answers

201,930 comments

95,354 users