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

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

• Note the distinction between "contains finite elements" and contains "finitely many elements". "Finite" isn't a number, and "contains finite elements" means "contains elements that are finite". Since all elements of $L(M)$ are finite by definition, "contains finite elements" probably isn't what you intended, so I edited. – David Richerby Nov 7 '18 at 21:47

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.

• Unless I missed something, I think your first hint is misleading: I can make $M'$ accept finitely many strings if $M(w)$ halts (and everything otherwise), but I can't make it accept nothing. This is enough to prove the reduction, but not in the way you suggest. – chi Nov 8 '18 at 12:33
• Maybe I've missed something! I'll have a look this evening, if I remember. – David Richerby Nov 8 '18 at 12:42