Prove $L = \{M \mid L(M)\text{ is infinite}\}$ is not Turing-recognizable

Question

I'm supposed to prove this through mapping reducibility. I think I'm supposed to show that $A_{\mathrm{TM}} \le_\mathrm{m}\overline{L}$, which means that $\overline{A_{\mathrm{TM}}}\le_\mathrm{m} L$ and, since $\overline{A_{\mathrm{TM}}}$ is not Turing-recognizable, then $L$ is not Turing-recognizable.

I think that $\overline{L} = \{M\mid L(M) \text{ is finite} \}$ and that it means that $L(M)$ contains a finite number of strings.

I don't know how to construct a Turing machine that can prove $A_{\mathrm{TM}}\le_\mathrm{m} \overline{L}$.

Answer 1

Recall that the input to the halting problem is a pair $(\langle M\rangle, w)$ and we must accept this input if $M(w)$ halts, and reject it otherwise.

We want to decide the halting problem by reduction to $\overline{L}$. That is, we need to produce a computable function $f$ that takes an input $(\langle M\rangle, w)$ and produces a string in $\overline{L}$ if $M(w)$ halts and a string that is not in $\overline{L}$ if $M(w)$ does not halt.

There's a small mistake in your reasoning in the question that's worth mentioning at this point, but it doesn't make any real difference. Strings in $L$ are descriptions of Turing machines that accept infinitely many inputs. That means that a string is in $\overline{L}$ if either it's a description of a Turing machine that only accepts finitely many inputs, or if it's not a description of any Turing machine at all.

However, we can ignore the strings that don't describe Turing machines and design a function $f$ such that $f(\langle M\rangle,w)$ is always the description of a Turing machine and that Turing machine accepts only finitely many inputs if $M(w)$ halts, and is one that accepts infinitely many inputs if $M(w)$ doesn't halt.

Hint: $\emptyset$ is finite and $\Sigma^*$ is infinite. Transform $(\langle M\rangle,w)$ into the string $\langle M'\rangle$ such that $M'$ will accept nothing if $M(w)$ halts and will accept everything if $M(w)$ doesn't halt.

There's another hint below, which you can see by mousing over the yellow box. But try to figure it out on your own, first.

Hint 2: the reduction is very similar to the one used to prove that the problem "Does $M$ halt on the empty input?" is undecidable.