and $L_{\leq k} = \{\langle M \rangle : |L(M)|\leq k\}$

The solution that I saw is:

Proof by contradiction, assume such $M$ exists.

So reduction $f$ from $\overline{HP}$ to $L(M)$, when $\overline{HP}=\{(\langle M\rangle,x ) | M $ doesn't halt on $ x\}$

$f(\langle M'\rangle,x ) = \langle M_x\rangle$

When $M_x$ on input $w$ implemented in the following way:

  1. execute $M'$ on $x$
  2. accept if M' halt

I can't understand the validity of it, I mean why

$M_x \in L(M) \Leftrightarrow (\langle M'\rangle,x )\in \overline{HP}$

is true?

The next step quite simple, if $M$ exists then $L(M)\in RE$ and based on the reduction it's mean that $\overline{HP}\in RE$, contradiction.

Maybe I found wrong solution?


1 Answer 1


To fix the solution you just need to accept any 3 elements of your choice in $M_x$. Now, $M_x$ will look something like that:

  1. If $w$ (the input) is $0,1$ or $00$, accept .
  2. Otherwise, emulate $M$ on $x$.
  3. Accept if $M$ halted.

Now, you are guaranteed to have exactly 3 elements in $L(M_x)$ if $M$ doesnt halt on $x$, and otherwise $L(M_x)=\Sigma^*$.

You can now continue with the proof as you have written.

  • $\begingroup$ Thank you man!! $\endgroup$ Commented Jul 4, 2021 at 18:59

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.