# Prove that the language of all Turing machines that accept finitely many words is decidable or not

Question: we have the following language: $$A = \{\langle M \rangle :| L( M)| < \infty \text{ and } M\text{ is a Turing machine}\}$$ where $$\langle M\rangle$$ is the encoding of $$M$$ and $$L(M)$$ is the language accepted by $$M$$. Prove $$A$$ is a decidable language or not.

My idea was to use reduction on this but I can't find the proper one and I don't even know if it is decidable or not.

• This problem is undecidable, and in fact it is $\Sigma_2^0$-complete, i.e., $L$ is not even recursively enumerable. Commented Jul 8, 2022 at 15:29
• @ReijoJaakkola Thank you. Can you please help me with proving it? Commented Jul 8, 2022 at 15:49
• Hint: Consider a Turing machine $T'$ that ignores its input, simulates some other Turing machine $T$ on some input $x$, and then halts and accepts. What can you say about $|L(T')|$? Commented Jul 9, 2022 at 12:43

We can reduce from $$A_{TM}$$ to prove $$A$$ is undecidable and also from $$\overline{A_{TM}}$$ to prove $$A$$ is unrecognizable. We proceed with the first claim. I recommend you pause here and think about how it could be done before moving forward. The core idea is excatly what Steven suggested that is to specify a Turing machine $$M'$$ to simulate another Turing machine $$M$$. (in the case of reduction from $$A_{TM}$$, the machine-input pair $$\langle M, w \rangle$$ has to be manipulated by $$M'$$ such that $$M'$$ accepts finitely many strings if and only if $$M$$ accepts $$w$$.) We can describe $$M'$$ informally as follows:
1. On input $$n \in 1^+$$ (namely reject all but unary representations)
2. Simulate $$M$$ on $$w$$ for at most $$n$$ steps. If $$M$$ halted and accepted during simulation, reject $$n$$. Otherwise accept $$n$$.
If $$M$$ accepts $$w$$ after $$k$$ steps, $$L(M')$$ would be $$\{1, 2, \dots, k - 1\}$$. Otherwise, $$L(M') = \mathbb{N}$$. Therefore $$\langle M, w \rangle \in A_{TM} \iff M' \in A$$ or $$A_{TM} \leq_m A$$. Similarly by swapping "accept" and "reject" in the description of $$M'$$, we obtain the mapping reduction $$\overline{A_{TM}} \leq_m A$$.