ITM · Recursively enumerable
Is n a perfect square? 1 + 3 + 5 + …
A square is a sum of consecutive odd numbers: 16 = 1 + 3 + 5 + 7. A ruler after a # starts with one mark; each round crosses off as many of the input’s 1s as the ruler has marks, then lengthens the ruler by two. The input is a square exactly when it runs out at the end of a round. The machine finds its left end by walking to a blank, so its tape extends both ways.
The author’s examples, run
ε → accept1 → accept1111 → accept111111111 → accept11 → reject111 → reject11111 → reject11111111 → reject
Behaviour
Halts from a blank tape after 1 steps, leaving 0 non-blank cells.