Solutions to ex3
================

(a) We reduce A_TM to L. For input <M,w> the function will return M'
such that M accept w iff M' accepts 01 or rejects 111


M' = "on input x
  if x = 111 accept
  otherwise simulate M on w and do the same
"

Now, if M accepts w then M' will accept all strings,
and so M' in L.
If M doesn't accept w, then M' will accept 111 and reject all other strings and so will not be in L.

(b) Since A_TM is undecidable, we learn that L is undecidable. We can also learn that L^c is undecidable as
A_TM^c <=m L^c.

(c) Here is a recognizer R for L
R = "on input <M>
 for i = 0..
 run M on 01 for i steps, and on 111 for i steps.
 if M accepted 01 or rejected 111 during those i steps ACCEPT
"
Notice that if M accepts 01 or rejected 111 it will happen after some finite number of steps
and so will be detected by the above loop. If neither of this are true, then R will never accept.
This makes M a recognizer for L.

(d) if A_TM <=m L^c then also A_TM^c <=m L, but this is impossible since A_TM is not recognizable and L is.