# 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
• Was thinking if this simple argument is valid: "keep generating strings infinitely on given alphabet and make Turing Machine dovetail on these strings. It may accept some and/or reject some strings. But, at any point in time, when TM has rejected some number of strings, we will never know if it will accept any string in future, making it impossible to say its language is infinite. Hence not recognizable." – anir Jan 14 '20 at 8:46