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.
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:
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$.
