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, A, ...), 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 kH : halt
+ i j
- i j k
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 = x, A = A = ... = 0.
Here are two sample programs:+ 1 2+ 1 3- 2 5 4+ 2 1H // outputs 4 (order: L1->L2->L3->L4->L1->L2->L3->L5)
+ 1 2+ 1 3- 2 5 4+ 2 1H // 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 8H // 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).