Is F decidable, Turing-recognizable, co-Turing-recognizable

Question

Let $F = \{\langle M \rangle : L(M)\} $, where $L(M)$ is finite.

So far I am operating under the assumption that the complement of the language is $F' = \{\langle M \rangle : L(M)\} $, where $L(M)$ is infinite.

Based on my notes from class here is what I have concluded so far:

Either $F$ is Turing recognizable or $F$ is co-Turing recognizable.

I either have to prove $F$ is Turing recognizable or $F'$ is Turing recognizable, but I am not sure how to draw a Turing machine for this. Am I on the right track? Any help is really appreciated.

Answer 1

Let $HP = \{\langle A,x \rangle :$ A is a TM that halts on x $\}$
and $\overline{HP} = \{\langle A,x \rangle :$ A is a TM that does not halt on x $\}$

Suppose $R$ is a recognizer for $F$.
The following reduction shows that $F$ is not Turing-Recognizable and hence not Decidable.

Loop = "On input <A, x>:
        1) M = "On input <w>
                10) simulate A on x
                20) accept
        2) if R accepts <M, w>
        3)     accept
        4) else
        5)     reject

A loops on x $\Leftarrow\Rightarrow$ M does not accept any strings $\Leftarrow\Rightarrow L(M)$ is empty and finite
If R recognizes F then Loop recognizes $\overline{HP}$
Since $\overline{HP}$ is not recognizable, F is not Turing-Recognizable.

Suppose $R$ is a recognizer for $F'$.
The following reduction shows that $F'$ is not Turing-Recognizable and hence that $F$ is not co-Turing recognizable.

Loop = "On input (A, x)
        1) M = "On input w
                10) simulate A on x for |w| steps
                20) if A halts on x in |w| steps
                30)    reject
                40) else
                50)    accept

        2) if R(M, x) accepts
        3)     accept
        4) else
        5)     reject

A loops on x $\Leftarrow\Rightarrow$ M accepts all strings $\Leftarrow\Rightarrow L(M)$ is infinite
If R recognizes $F'$ then Loop recognizes $\overline{HP}$
Since $\overline{HP}$ is not recognizable, $F'$ is not Turing-Recognizable.
Hence, $F$ is not co-Turing-Recognizable.