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

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.

## 1 Answer

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.