1
$\begingroup$

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?

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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