Library

TM · Recursively enumerable

Binary addition a+b

@thethinkmachine·version 1·CC BY 4.0·added 28 Sept 2026

Computes a+b on the tape by transferring one unit per lap: decrement b, increment a, repeat; when b hits zero it is erased and the sum sits where a was.

Open in AutomataStudio
More
Open in the desktop app Download the .automaton file Source on GitHub
seek +b > 0?b endb −1returna +1erase bacc
The machine as drawn — 8 states, 18 transitions.

The author’s examples, run

1011+11 → accept10+1 → accept1001+101 → accept11 → reject+11 → reject

Behaviour

The first steps from a blank tape: one row per step, time running down; the outlined cell is the head.

Halts from a blank tape after 0 steps, leaving 0 non-blank cells.