Library

TM · Recursively enumerable

Unary addition

m ones, a plus sign, n ones: turn the + into a 1 and erase the last 1. The tape then holds m + n ones — addition in unary is a two-symbol edit, which is why the first machines in every course use it.

scanrighterasedone1 → 1, R+ → 1, R1 → 1, R⊔ → ⊔, L1 → ⊔, S
The machine as drawn — 4 states, 5 transitions.

The author’s examples, run

+ → accept1+11 → accept+1 → accept1111+111111 → accept1 → reject++11 → reject11 → reject+111+111111 → 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 1 steps, leaving 0 non-blank cells.