This is the fourth part of the Turing Machine series. For your convenience you can find other parts in the table of contents in Part 1 – Addition

Today we subtract two numbers. This is very similar to addition so should be pretty readable.

States:

q0 - looking for the beginning, no borrow
q1 - looking for the beginning, with borrow
q2 - looking for the first number digit, no borrow
q3 - looking for the first number digit, with borrow
q4 - 0 from the first digit, looking for boundary, no borrow
q5 - 1 from the first digit, looking for boundary, no borrow
q6 - 1 from the first digit, looking for boundary, with borrow
q7 - 0 from the first digit, looking for the second number digit, no borrow
q8 - 1 from the first digit, looking for the second number digit, no borrow
q9 - 1 from the first digit, looking for the second number digit, with borrow
q10 - 0 in the difference, looking for the end of the second number, no borrow
q11 - 1 in the difference, looking for the end of the second number, no borrow
q12 - 1 in the difference, looking for the end of the second number, with borrow
q13 - 0 in the difference, looking for the end of the second number, with borrow
q14 - 0 in the difference, looking for a place to write, no borrow
q15 - 1 in the difference, looking for a place to write, no borrow
q16 - 1 in the difference, looking for a place to write, with borrow
q17 - 0 in the difference, looking for a place to write, with borrow

The input looks like this:

$aaaa%bbb^

Transition table:

0,q0,0,q0,L
1,q0,1,q0,L
^,q0,^,q0,L
%,q0,%,q0,L
$,q0,$,q2,R

0,q1,0,q1,L
1,q1,1,q1,L
^,q1,^,q1,L
%,q1,%,q1,L
$,q1,$,q3,R

0,q2,$,q4,R
1,q2,$,q5,R

0,q3,$,q6,R
1,q3,$,q4,R

0,q4,0,q4,R
1,q4,1,q4,R
%,q4,%,q7,R

0,q5,0,q5,R
1,q5,1,q5,R
%,q5,%,q8,R

0,q6,0,q6,R
1,q6,1,q6,R
%,q6,%,q9,R

0,q7,%,q10,R
1,q7,%,q12,R
%,q7,%,q7,R

0,q8,%,q11,R
1,q8,%,q10,R
%,q8,%,q8,R

0,q9,%,q12,R
1,q9,%,q13,R
%,q9,%,q9,R

0,q10,0,q10,R
1,q10,1,q10,R
^,q10,^,q14,R

0,q11,0,q11,R
1,q11,1,q11,R
^,q11,^,q15,R

0,q12,0,q12,R
1,q12,1,q12,R
^,q12,^,q16,R

0,q13,0,q13,R
1,q13,1,q13,R
^,q13,^,q17,R

0,q14,0,q14,R
1,q14,1,q14,R
.,q14,0,q0,L

0,q15,0,q15,R
1,q15,1,q15,R
.,q15,1,q0,L

0,q16,0,q16,R
1,q16,1,q16,R
.,q16,1,q1,L

0,q17,0,q17,R
1,q17,1,q17,R
.,q17,0,q1,L