Originally Posted by

**crazyautomata101** Thank you very much for your reply! I feel like my mind is trapped somewhere since I just don't see the reduction. I read the language as {M | M is a machine with less than 101 states and accepts any input}. For L1, I got a reduction:

We know the halting problem "given a machine M and input x, does M halt on x". Now construct a new machine M': if the input = x, then run M on x, if it halts, accept. If input != x, accept the input. We can see M' accepts any input iff M halts on x. And M' doesn't accept everything iff M does not halt on x. So we got the reduction. L1 is undecidable. Now I got this gap since the number of states in M is unbounded. If we put limit on the number of states in M', then essentially we are reducing from 100-State-HALT instead of the original HALT. For example, M is with 1000 states and M' will be rejected regardless whether M halts on x or not.

Like I said, I hope I'm just mistaking something so there is an easy reduction. Would you please elaborate your idea:

Any comment will be appreciated! Thank you StaryNight