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.
The author’s examples, run
abc → acceptaabbcccc → acceptaabcc → acceptaaabbcccccc → acceptbbc → rejectbabbcccc → rejectbabcc → rejectbaabbcccccc → reject
Behaviour
Halts from a blank tape after 1 steps, leaving 0 non-blank cells.