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?

  • $\begingroup$ $M_w$ is the binary-coded Turingmachine. $\endgroup$ – Amith Mar 18 '18 at 15:03

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.