Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
If it is decidable, let $M$ decide it.
Construct a decider $D$ that works on input $\langle w_1,w_2\rangle$ as follows:
Construct $M_w$ (as well as its encoding $w$) that works on input $x$ as follows:
Run $M_{w_1}$ on $w_2$.
Accept.
Run $M$ on $w$.
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.
