Library

TM · Recursively enumerable

Unary multiplication

Input 1ᵐ*1ⁿ; output 1ᵐ*1ⁿ#1ᵐⁿ. For each 1 of the first number the machine copies the whole second number to the end of the tape, one 1 per trip, marking what it has used with X and Y and restoring them afterwards. Multiplication as repeated addition, at walking pace.

starttoStarzerodonepicktoEndrestoretoOutbacknextXstartNextunmark1 → X, R* → *, R1 → 1, R⊔ → #, S1 → 1, R* → *, RY → Y, R1 → Y, R# → #, L⊔ → #, L1 → 1, R# → #, R⊔ → #, R1 → 1, R⊔ → 1, L1 → 1, L# → #, LY → Y, RY → 1, L* → *, L1 → 1, LX → X, R1 → X, R* → *, LX → 1, L1 → 1, S
The machine as drawn — 12 states, 26 transitions.

The author’s examples, run

* → accept1*11 → accept*1 → accept111*11111 → accept1 → reject**11 → reject11 → reject*11*11111 → 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.