Library

TM · Recursively enumerable

Multiplication checked: aⁱbʲcᵏ with k = i·j

Sipser’s third example. After checking the shape a⁺b⁺c⁺, the machine takes the a’s one at a time; for each, it crosses off one c per b, marking the b’s and then restoring them. The c’s run out exactly when k = i·j.

a → A, Ra → a, Rb → b, Rb → b, Rc → c, Rc → c, R⊔ → ⊔, La → a, Lb → b, Lc → c, LA → A, Sa → x, RA → x, Ra → a, Rb → y, Rb → b, Rz → z, Rc → z, Lz → z, Lb → b, Ly → y, Rb → y, Rz → z, Ly → b, La → a, Lx → x, Ra → a, Lx → x, Rb → b, Rz → z, R⊔ → ⊔, S
The machine as drawn — 14 states, 31 transitions.

The author’s examples, run

abc → acceptaabbcccc → acceptaabcc → acceptaaabbcccccc → acceptbbc → rejectbabbcccc → rejectbabcc → rejectbaabbcccccc → 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.