0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.