Missing step in Turing Machine
We want to design a Turing Machine that adds 1 to a binary number. The machine processes the number from right to left, following these rules:
- Start at the rightmost bit.
- If the current bit is 0: Flip it to 1 and halt.
- If the current bit is 1: Flip it to 0 (because 1 + 1 causes a carry) and move left to process the next bit.
- If the machine moves left beyond the leftmost digit (i.e. encounters a blank): Write a 1 to represent the carried bit and halt.
The following state diagram attempts to capture these steps but is missing a critical transition. Identify the missing step.

This exercise is part of the course
Concepts in Computer Science
Hands-on interactive exercise
Turn theory into action with one of our interactive exercises
