Question

Show that the language F={M| M is a Turing machine , and L(M) contains infinite elements} is not Turing recognizable.

Answer 1

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

A non-halting problem is given as follows: Given an encoding of TM 〈H〉〈H〉 and a word w,w, whether HH does not halt on w.w. That is, we have to decide if HH does not halt on w.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),(〈H〉,w), we proceed as follows: We make a new TM say M,M, which on input x,x, just simulates HH on ww for |x||x| steps. If HH halts on w,w, MM goes to reject state. Otherwise, it accepts. So, L(M)=Σ∗L(M)=Σ∗ if HH does not halt on ww and L(M)=L(M)= a finite set if HH halts on w.w. (If HH halts for w in say kk steps, any string with length greater than |k|,|k|, would certainly be not in LL (as we are running for only |x||x| steps for input x),x), making LL a finite set).

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

Proving L′L′ is not RE is easy.
L′={〈M〉∣L(M)L′={〈M〉∣L(M) is finite}}

L(M)L(M) is finite is a non-monotonic property of TM. Because we can take TM TyesTyes with L(Tyes)=ϕL(Tyes)=ϕ and TnoTno with L(Tno)=Σ∗L(Tno)=Σ∗. Here, TyesTyes satisfies the property (of being finite) and TnoTno does not satisfy the property and L(Tyes)⊂L(Tno)L(Tyes)⊂L(Tno), making this a non-monotonic property of TM. And hence this becomes not RE as per Rice's theorem second part.

So, both LL and L′L′ are not RE