TM · Recursively enumerable
Which binary number is smaller? x#y
Two binary numbers of the same length; accept when the first is smaller. The machine compares them digit by digit from the most significant end, crossing off as it goes. The first difference decides the answer, but it keeps crossing in pairs after that, because the lengths still have to match.
The author’s examples, run
0#1 → accept001#010 → accept00#11 → accept000011#110011 → accept1#1 → reject101#010 → reject#0#11 → reject#00011#110011 → reject
Behaviour
Halts from a blank tape after 1 steps, leaving 0 non-blank cells.