A few notes on A2
-----------------

1. When we write E_TM = { <M> : L(M) = empty }, you have to realize that
there are two different languages that we are talking about.

First of all, E_TM is a language and it contains several encodings of TMs.
Strings like epsilon, 0, 110, 000101 do not belong to E_TM because they are
not encodings of TMs. However, E_TM is not empty!

For example, take the TM R defined by
d(q_0,0) = q_rej,
d(q_0,1) = q_rej,
d(q_0,_) = q_rej.
This TM is an example of a TM such that L(R)=empty, so <R> is in E_TM.

The second language the definition of E_TM is talking about is L(M).
Every TM M has a unique language associated with it, called L(M).
This is the language of all strings that M accepts.

In light of these two facts, you should realize that statements like the ones
below are incorrect:

- "<M> belongs to E_TM, therefore L(M)=E_TM"
- "E_TM is the empty language"


2. If you are having trouble digesting proofs that involve TMs building
other TMs as part of their computation, always think of the parallel to C
programs, as laid out in question 3 of A2.

For example,

"M_f: on input <M,w>
      build a TM M' such that
        M': on input x
            ignore x
            run M on w
            if M accepts, M' REJECTS
            if M rejects, M' ACCEPTS
      output <M'>"

Note: I don't know what the thing above is doing! I'm just using it
as an example.

So, if the TM above looks weird, maybe seeing the equivalent C code would help:

char *f(char *M, char *w) {
  char *M' = new char[strlen(M) + strlen(w) + 500];
  M' = "int M'(char *x) {\n" +
       "  int result = run(" + M + ", " + w + ");\n" +
       "  return(result == 0? 1 : 0);\n" +
       "}\n";
  return(M');
}

Note: we are using the function "run" that we mentioned in A2Q3.
Note2: my C/C++ syntax is rusty, but you get the idea.