Library

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 machine as drawn — 15 states, 33 transitions.

The author’s examples, run

ε → accept1 → accept1111 → accept111111111 → accept11 → reject111 → reject11111 → reject11111111 → 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.