Decidability of checking whether all words accepted by a TM have an even number of 1s

Question

Let $\Sigma = \{0,1\}$, and consider the language $$L = \{\langle M \rangle \mid M \text{ is a TM and } L(M) \text{ is a subset of } Σ^* \text{ and all strings in this set have an even number of 1s}\}.$$

I think $L$ is undecidable. But I am stuck on proving it. I think it is equivalent to prove $L = \{\langle M \rangle \mid M \text{ is a TM and } L(M) \text{ is a specific set with an even number of 1s}\}$ is undecidable. How can I do some reduction for it?

Answer 1

First, it can be shown easily by Rice's theorem.

Alternatively, you can show a reduction from $\overline{HP}$ as follows:

$$f(\left< M \right>,x)=\left<M_x\right>$$

$M_x$ on input $w$:

1. run $M$ on $x$ for $|w|$ steps.
2. if M stopped then accept.
3. if the number of 1's in $w$ is even then accept, otherwise reject.

I'll let you verify the correctness.