The string that you emailed me:

 

(18P) Complete the string to make it a theorem in the pq-system: ---pq-------

(17P) What is the term describing a connection between two complex structures, such that a part and its corresponding counterpart always play a similar role in their own structures? (Hint: hw last week)

(25P) What is the answer of Mr. T's infernal riddle (regarding the dialogue at pp.61)?

 

(9NP) 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

i

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).