Specimen answer to quiz 1 question 4.


 Move left to right gathering 3 bits
 Notation (abc)dR
   where a is 0 or 1 (a carry bit),
         b is either ? searching for bit on left
         x bit found (value absorbed into d)
         - no bit on left, equivalent to 0
	 c is either ? searching for bit on right
         z bit found absorbed into d
         - is no bit on right, equivalent to 0
         d is 0,1,2,3 sum of 3 bits
   (1/0)L means go left with/out carry

 No check for input validity.  On invalid input it may halt
 with no useful output.
 Bits on left (of comma) are covered by x, on right by z.

 (abc)d R once b and c are not ?, the action depends only on d.
  This gives us

 (0/1 ?/x/- ?/y/-) ... R

 (0 x/- y/-)0 R        append a no carry: q4
   (0 x/- y)1 R        append b no carry: q5
   (0 x y|-)1 R        append b no carry: q5
    (0 -  -)0 finished

 (1 x/- y/-)1 R        append b no carry: q5

   (1 x/- y)2 R        append a and carry: q8
   (1 x y|-)2 R        append a and carry: q8
   (1 x y ) 3 R        append b and carry: q13
   (1 -  -)1 R nearly finished

   return without carry: q6
   return with carry : q9
  

q0 0 x R q1     q1: (0x?)0 R
q0 1 x R q2     q2: (0x?)1 R

q1 0 0 R q1     (0x?)0 R
q1 1 1 R q1     (0x?)0 R
q1 , , R q3     q3: (0x?)0 R, past comma

q3 z z R q3     (0x?)0 R
q3 0 z R q4     q4: (0xz)0  append a no carry
q3 1 z R q5     q5: (0xz)1  append b no carry

q4 0 0 R q4     () 0 R
q4 1 1 R q4
q4 a a R q4
q4 b b R q4
q4 B a L q6     a appended, q6: return no carry

q5 0 0 R q5     () 1 R
q5 1 1 R q5
q5 a a R q5
q5 b b R q5
q5 B b L q6     b appended, q6: return no carry

q6 0 0 L q6     q6: (0) L
q6 1 1 L q6
q6 a a L q6
q6 b b L q6
q6 z z L q6
q6 , , L q6
q6 x x R q0    resume q0

 q2: (0x?)1 R

q2 0 0 R q2     (0x?)1 R
q2 1 1 R q2     (0x?)1 R
q2 , , R q7     q7: (0x?)1 R, past comma

q7 z z R q7     (0x?)1 R
q7 0 z R q5     q5: (0xz)1  append b no carry
q7 1 z R q8     q8: (0xz)2  append a and carry

q8 0 0 R q8     () 2 R
q8 1 1 R q8
q8 a a R q8
q8 b b R q8
q8 B a L q9     a appended, q9: return with carry

q9 0 0 L q9     q9: (1) L  return with carry
q9 1 1 L q9
q9 a a L q9
q9 b b L q9
q9 z z L q9
q9 , , L q9
q9 x x R q10    q10: (1??) 1 R

q10 x x R q10
q10 0 x R q2    (1x?) 1 R --- q2
q10 1 x R q11   q11: (1x?) 2 R 

q11 0 0 R q11     (1x?)2 R
q11 1 1 R q11     (1x?)2 R
q11 , , R q12     q12: (0x?)2 R, past comma

q12 z z R q12     (0x?)2 R
q12 0 z R q8     q8: (0/1 xz)2  append a and carry
q12 1 z R q13    q13: (1xz)3 append b and carry

q12 a a R q8
q12 b b R q8

q13 0 0 R q13   (1xz) 3 R
q13 1 1 R q13
q13 a a R q13
q13 b b R q13
q13 B b L q9    (1xz)3 b appended return with carry

q0 , , R q14    (0-?) 0 R: q14
q10 , , R q15   (1-?) 1 R: q15

q14 z z R q14  (0-?) 0 R
q14 0 z R q4   (0-z) 0  append a no carry
q14 1 z R q5   (0-z) 1 append b no carry

q14 a a R q16  (0--) 0 finished, clean up: q16
q14 b b R q16 

q15 z z R q15  (1-?) 1 R
q15 0 z R q5   (1-z) 1 append b no carry
q15 1 z R q8   (1-z) 2 append a with carry
q15 a a R q5   (1--) 1 R append b with carry
q15 b b R q5

q16 a a R q16
q16 b b R q16
q16 B B L q17

q17 a 0 L q17
q17 b 1 L q17
q17 z z L q18

q18 z z L q18
q18 , , L q18
q18 x x L q18
q18 B B R q19

q19 x B R q19
q19 , B R q19
q19 z B R q19