Labs / Computer Science
Turing Machine
This little machine knows exactly one trick: add one to a binary number. It has no memory beyond a single state letter and the symbol under its head, yet those simple rules are enough to do arithmetic. Press Play to watch it work, or click cells to write your own number and run it again.
state S · scan rightsteps 0head 0value 0
What to try
- Follow the highlighted rule in the table. Can you predict where the head will move before the machine does it?
- Increment 255. Why does the machine have to walk all the way back to the left, and where does the new leading 1 come from?
- How many steps does adding one take for a short number versus a long one? What makes some numbers so much slower than others?
- Draw a number that is all 1s, like 1111. What happens to every digit as the carry ripples through?
- The machine never stores the number anywhere but the tape. How does it remember whether it is still carrying, using only the states S and C?