The string that you emailed me:

(20P) Who is a jerk? (according to pp. 75-81) Achilles Tortoise Crab

(100P) (Due at the second last class, partial credits) Choose one of the two options:
Figure and Ground project: Compose some art in which both the figure and the ground are interesting.
Tessellation project: Compose a nice tessellation.

We extended the pq-system to contain more typographical patterns such as (t,q) and DND (doesn't divide). When you're asked to define things, you're free to use (p,q), (t,q) and DND as if they are already defined correctly, plus any previous definition (doesn't matter whether you defined that correctly).

For format's sake, let's say we defined (p,q) as follows: (you can omit the periods in your definitions)

xpyqz -> xpy-qz-.

(15P) In 1 line, define LT such that "(x hyphens)LT(y hyphens)" is a theorem iff x < y.  (Yes it fits!)

(25P) Define P such that "P(x hyphens)" is a theorem iff x is a prime. (Recall: do a bounded search using DND.)


(40NP) Define POT such that "POT(x hyphens)" is a theorem iff x is a power of 10.

(70NP) Define SF such that "SF(x hyphens)" is a theorem iff x is square free.

(200NP) In view of this week's topic (Figure and Ground), try to figure out how the following sequence is generated (no need to explain):

1, 3, 7, 12, 18, 26, 35, 45, 56, 69, 83, 98, 114, ...

Then define HOFSEQ such that "HOFSEQ(x hyphens)" is a theorem iff x is in this sequence.

(?NP) I would really like to see the following:

1. "PERF(x hyphens)" is a theorem iff x is a perfect number.

2. "BACHRIGHT" is a theorem iff Goldbach's conjecture is true.

3. "BACHWRONG" is a theorem iff Goldbach's conjecture is false.

4. "COLLATZRIGHT" is a theorem iff the 3x+1 conjecture is true.

5. "COLLATZWRONG" is a theorem iff the 3x+1 conjecture is false.

Play around. If your answer is nonempty and provably-correctly defines k of them, you will get 15^kNP. (Hence you get some small reward by simply reading this.)

(16NP) 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):