The request
“Draw a Turing machine that adds one to a binary number: qScan moves right over 0 and 1, moves left on blank B, qCarry changes trailing 1s to 0 while moving left, then changes a 0 or leading blank to 1 and accepts.”
Then tryAdd a reject state for an input symbol other than 0 or 1.Change the final move from stay to move right.
What is in this drawing
Read the decisions behind it.
01Right scan
qScan finds the right edge of the binary word.
02Carry loop
every trailing 1 becomes 0 while the carry moves left.
03Overflow case
a blank becomes 1 when the input contains only 1s.
Use this state pattern to explain how a Turing machine implements binary addition one tape cell at a time.
More like this
Other examples in this family.
FAQ
Common questions
Why are trailing 1s changed to 0?
Adding one to a binary 1 produces 0 with a carry into the digit to its left.
What happens to 111?
The carry runs past the left edge and writes a new 1, producing 1000.
Why does qScan move right first?
Binary addition starts at the least significant digit, which is at the right end of the input.