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 kH : halt
+ i j
- i j k
H
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 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).