For each of the following, indicate whether the problem is in P, NP, decidable, semi-decidable (recognizable), or none of these.

1. { n : M_n(n) halts in no more than n steps }

2. { n : M_n(n) halts in more than n steps }

3. { n : M_n halts on at least 3 inputs }

4. { n : M_n halts on at most 3 inputs }

5. { n : M_n has an even number of states }