1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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.