Two-tape TM as binary adder

Setup. Tape 1 holds binary number A and tape 2 holds binary number B (most significant digit on the left, blanks elsewhere), each head starting on the leftmost digit. The sum is written on tape 1 (overwriting A); tape 2 is unchanged. S means the head stays.

Idea. Add from the least significant digit, as in school arithmetic, carrying through the state. A blank counts as 0.

1. Phase 1 (state q0): move each head to the right end of its own number (a head that already sees a blank stays).
2. Phase 2 (states c0, c1 = carry 0 or 1): read (x, y), compute s = x + y + carry; write s mod 2 on tape 1; the new carry is s div 2; move both heads left (head 2 stays when on a blank).
3. When both heads read blank: if the carry is 1, write 1 on tape 1; halt.

M has states {q0, c0, c1, qa} and tape alphabet {0, 1, ⊔}. Rules (digit x on tape 1, y on tape 2):

In the c0/c1 digit rows a blank is treated as 0 (for example (⊔,1) behaves as (0,1)), and head 2 stays instead of moving left once it reads a blank.

 ──► (q0) ──(both ⊔) L,L──► (c0) ◄──► (c1)
     ↺ moves heads            │          │
       to the right ends      └─(⊔,⊔)─► ((qa))

Example: 101 + 11 (5 + 3 = 8)

digit  x y  carry  write  new carry
 1     1 1    0      0       1
 2     0 1    1      0       1
 3     1 ⊔    1      0       1
 end   ⊔ ⊔    1      1  (write carry)

Tape 1 becomes 1000 = 8. First q0 runs both heads to the right ends; each row above is then one move of the adder states. The machine runs in about 2·max(|A|, |B|) steps.