3. (8 points)

1. (a) Prove that the set 4stTM ={M|MisaTMandMhasexactly4states}

   is recognizable by specifying a Turing machine that recognizes it, and briefly justifying your construction.

2. (b) Prove that the set NonETM = {M | M is a TM and L(M) is nonempty}

   is recognizable by specifying a Turing machine that recognizes it, and briefly justifying your construction.

3. (8 points) (a) Prove that the set 4stTM-(M) I M is a TM and M has exactly 4 states) is recognizable by specifying a Turing machine that recognizes it, and briefly justifying your construction (b) Prove that the set Non ETA,-{(M | M is a TM and L(M) is nonempty} is recognizable by specifying a Turing machine that recognizes it, and briefly justifying your construction