scan seen1 done put0 check fix stepL 0 → 0, R 1 → 1, R ⊔ → ⊔, S 1 → 1, R 0 → 1, L ⊔ → ⊔, S 1 → 0, L 1 → 0, R 0 → 0, R 0 → 1, L 0 → 0, L
The machine as drawn — 7 states, 11 transitions.
The author’s examples, run ε → accept 00110 → accept 0 → accept 000000110 → accept
Definition $$ \begin{aligned} M &= (Q, \Sigma, \Gamma, \delta, q_0, F) \\Q &= \{ \text{scan}, \text{seen1}, \text{done}, \text{put0}, \text{check}, \text{fix}, \text{stepL} \} \\\Sigma &= \{ \text{0}, \text{1} \} \\\Gamma &= \{ \text{0}, \text{1}, \text{w}, \text{ }, \text{=}, \text{>}, \text{[}, \text{.}, \text{]}, \text{s}, \text{o}, \text{r}, \text{t}, \text{(}, \text{)}, \text{j}, \text{i}, \text{n}, \text{'}, \text{$\sqcup$} \} \\q_0 &= \text{scan} \\F &= \{ \text{done} \} \\\delta &: Q \times \Gamma \to Q \times \Gamma \times \{L, R, S\} \end{aligned} $$
Verified by the library ✓ Halts — 1 steps ✓ Tests pass — 4 examples checked ✓ Deterministic
Machine code tm.01.%20'()%2E%3D%3E%5B%5Dijnorstw@h:00SZ01RA02RB---------------------------------------------------_00SZ02LC02RB---------------------------------------------------_------01LD---------------------------------------------------_---01RA01RE---------------------------------------------------_---02LF------------------------------------------------------_---01LD------------------------------------------------------
Size 7 states · 11 transitions Level Intermediate Licence Creative Commons Attribution 4.0 Tags sorting computing-a-function insertion-sort