How to reduce halting problem to the problem of whether a Turing Machine accepts infinitely many inputs?

Question

The language $\{w \mid w \in \{0,1\}^{*}\text{ and }M_w\text{ accepts infinitely many inputs}\}$ is undecidable, where $M_w$ is the Turing machine represented by $w$.

I am confused because I do not know how to reduce this problem. Maybe it works with the complement of the Halting problem?

Answer 1

If it is decidable, let $M$ decide it.

Construct a decider $D$ that works on input $\langle w_1,w_2\rangle$ as follows:

1. Construct $M_w$ (as well as its encoding $w$) that works on input $x$ as follows:

   1. Run $M_{w_1}$ on $w_2$.

   2. Accept.

2. Run $M$ on $w$.

3. If $M$ accepts, accept; otherwise, reject.

We can see $D$ accepts if and only if $M$ accepts $w$, i.e. $M_w$ accepts infinitely many inputs, which means $M_{w_1}$ halts on $w_2$. Therefore $D$ is a decider for the halting problem, a contradiction.

Hence the language given in OP is undecidable.