1. L2 non-empty tells us there is some string x in L2. L2 not equal to Sigma* 
tells us there is some string y not in L2. Therefore, we can make a mapping as
 follows:

On input w...
1. Check using a decider for L1 whether w is in L1.
2. If so, output x.
3. Otherwise, output y.

So if w is in L1, f(w)=x is in L2. Otherwise, if w is not in L1, f(w)=y is not
 in L2.

2a). This language is unrecognizable. We can show this by showing A_TM reduces
 t L1^c (and so A_TM^c reduces to L1).

Recall that we need a mapping f:<M,w> -> <M1,M2> s.t. <M,w> in A_TM iff 
<M1,M2> in L1^c. 

In descriptive terms, M accepts w iff L(M2) /subset L(M1)

We do this as follows. Let M_REJECT be the machine that rejects all inputs, 
and M_w be the machine that on any input, ignores the input and runs M on w 
(if M halts on w, M_w also halts and with the same accepting/rejecting result 
as M).

Then f does the following:

On input <M,w>
1. Build M_w as described above.
2. Build M_REJECT as described above.
3. Output <M_w, M_REJECT>.

We verify:

If M accepts w then M_w also accepts. In particular, this tells us that on any
 input x, M_w will accept (since the output of M_w is dependent only on M 
running on w, not on x). Therefore L(M_w) is nonempty so L(M_REJECT)=<empty 
language> is a strict subset of L(M_w), hence <M_w, M_REJECT> is in L1^c.

Otherwise, if M rejects w or loops on w, then M doesn't accept anything. In 
this case we see that L(M_w)=L(M_REJECT) and so <M_w,M_REJECT> is not in L1^c.

Since A_TM <= L1^c, one of our theorems tells us that A_TM^c <= L1. We also 
know that A_TM^c is unrecognizable and so L1 mustn't be recognizable.

2b) Note that if a machine only runs for < 363 steps, it cannot read all the 
input of any strings with length beyond 362 symbols (each input being read 
requires one step of computation). This greatly limits the number of strings 
that we must "feed" to an input <M> in testing whether M halts within 362 
steps. 

Noting that Sigma* can be ordered lexicographically, we decide L2 as follows:

On input <M>... (Note, assuming our input is of proper form, else we'd reject)
1. Take the lexicographically jth word, w_j, in Sigma*
2.    for i = 1 to 362
3.       Run M on w_j for i steps. If M halts, we ACCEPT.
4.    next i
5. next w_j
6. REJECT 

One verifies that this machine decides L2.

3. The main idea as seen in tutorial is that we have two types of loops:

i) repeated configurations 
- for these, we can keep a separate tape during simulation of a machine M on 
blank input which will record all unique configurations we've seen
- during simulation, we look up transitions into new configurations and reject
 if a configuration is about to be repeated (identifying a loop in the 
simulation of M on blank)

ii) infinite tape looping (e.g. looking for a symbol on the tape in rightward 
direction but not finding it, or looking for a blank symbol to the right 
somewhere and going infinitely to the right, past all of the relevant tape 
content)


We saw how to use R(n) to detect type ii). Recall that 
HALT_BLANK={<M> | M halts on blank input} is undecidable. Being able to 
detect both types of loops and simulating M on blank as long as no loop is 
detected, we can decide HALT_BLANK.

Roughly, we do this as follows. Assume R(n) is computible, and let M_R 
compute it.

On input <M>... // Again, assuming valid encoding otherwise we'd reject
1. Determine how many states n are in M. If n=1, the case is trivial.
2. Use M_R to determine R(n-2). 
3. SImulate M on blank, using a separate tape to detect loop type i) and 
bounding the amount of tape to be used by R(n-2).
4. Output ACCEPT if we didn't detect a loop above.

4. Note that the language is of the proper form: L = {<M> | L(M) has property 
P}.

The property is non-trivial: we can have a language without it (e.g. the 
machine that accepts nothing) and a language with it (e.g. the machine that 
accepts the first 715 strings over {0,1}, lexicographically-speaking).

Therefore, L is undecidable.