# Does TM $M$ exist, when $L_{\leq3} \subset L(M) \subset L_{\leq4}$

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?

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^*$$.