The string that you emailed me:

(35P) We mentioned in class that we should not confuse inference rules with the actual theorems. How does this week's dialogue (pp. 43-45) illustrate this point?

(20NP) Using the derivation rules in the MU pizzle, if some string x can derive another string y, does that mean y can also derive x? Prove your answer. (Hint: CMU)

(21NP) In the MU pizzle, derive MIUI (from MI).

(22NP) Consider a variant(?) of the MU puzzle. The start and the goal are the same (MI to MU), but the rules have changed:
Rule I: You can remove a trailing I. (xI → x)
Rule II: If you have a string that is M plus two identical copies of a same string, you can delete one of the copies and get the resulting string. (Mxx → Mx)
Rule III: You can replace an I with UUU. (xIy → xUUUy)
Rule IV: You can insert II anywhere in a string you already have and get that string. (xy → xIIy)

Anything interesting about this puzzle? (Hint)

(4NP) Consider a programming language which represents the memory as an integer list (denoted as A[1], A[2], ...), and has three kinds of instructions (all of which takes up a whole line):

+ i j   : increment A[i] by 1, and go to line j
- i j k : if A[i] is positive, decrement A[i] by 1 and go to line j; otherwise, go to line k
H       : halt

When a program is executed, the memory is set to all zeros; then the instruction at line 1 is executed. A program is said to output x if it terminates with A[1] = x, A[2] = A[3] = ... = 0. 

Here are two sample programs:
+ 1 2
+ 1 3
- 2 5 4
+ 2 1
H      // outputs 4 (order: L1->L2->L3->L4->L1->L2->L3->L5)

+ 2 2
+ 2 3
+ 1 4
- 2 5 10
- 1 6 8
+ 3 7
+ 3 5
- 3 9 4
+ 1 8
H      // outputs 4

Within 15 lines, write a program whose output is greater than .
 Output (in decimal): 

(10NP) (Meta-problem. Partial credits given.) Predict two problems that will appear on next week's homework (remember to predict their values).