Library

TM · Recursively enumerable

Sipser’s M4: are the strings all different?

Input #x₁#x₂…#xₗ, each xᵢ a binary string; accept if no two are equal. Two of the #s carry marks (x and y) naming the pair being compared; the machine compares the strings after them by zigzagging, then moves the marks on to the next pair, until every pair has been checked.

sm2accc0c1g0g1ldlrh0rsh1advadv2adv3adv4adv5
The machine as drawn — 17 states, 80 transitions.

The author’s examples, run

#0#1 → accept#01#10#11 → accept#0#01#1 → accept#1#1 → reject#0#1#0 → reject## → reject# → accept#10#10#0 → 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.