Show HN: Bubble sort on a Turing machine

12 points

4 months ago

Bubble sort is pretty simple in most programming languages ... what about on a Turing Machine? I used all three of Claude 4.6, GLM 5, and GPT 5.2 to get a result, so this exercise was not quite trivial, at least at this time. The resulting machine, bubble_sort_unary.yaml, will take this input:

111011011111110101111101111

and give this output:

101101110111101111101111111

I.e., it's sorting the array [3,2,7,1,5,4]. The machine has 31 states and requires 1424 steps before it comes to a halt. It also introduces two extra symbols onto the tape, 'A' and 'B'. (You could argue that 0 is also an extra symbol because turinmachine.io uses blank, ' ', as well).

When I started writing the code the LLM (Claude) balked at using unary numbers and so we implemented bubble_sort.yaml which uses the tape symbols '1', '2', '3', '4', '5', '6', '7'. This machine has fewer states, 25, and requires only 63 steps to perform the sort. So it's easier to watch it work, though it's not as generalized as the other TM.

Some comments about how the 31 states of bubbles_sort_unary.yaml operate:

  | Group | Count | Purpose |
  |---|---|---|
  | `seek_delim_{clean,dirty}` | 2 | Pass entry: scan right to the next `0` delimiter between adjacent numbers. |
  | `cmpR_*`, `cmpL_*`, `cmpL_ret_*`, `cmpL_fwd_*` | 8 | Comparison: alternately mark units in the right (`B`) and left (`A`) numbers to compare their sizes. |
  | `chk_excess_*`, `scan_excess_*`, `mark_all_X_*` | 6 | Excess check: right number exhausted — see if unmarked `1`s remain on the left (meaning L > R, swap needed). |
  | `swap_*` | 7 | Swap: bubble each `X`-marked excess unit rightward across the `0` delimiter. |
  | `restore_\*` | 6 | Restore: convert `A`, `B`, `X` marks back to `1`s, then advance to the next pair. |
  | `rewind` / `done` | 2 | Rewind to start after a dirty pass, or halt. |

(The above is in the README.md if it doesn't render on HN.)

I'm curious if anyone can suggest refinements or further ideas. And please send pull requests if you're so inclined. My development path: I started by writing a pretty simple INITIAL_IDEAS.md, which got updated somewhat, then the LLM created a SPECIFICATION.md. For the bubble_sort_unary.yaml TM I had to get the LLMs to build a SPEC_UNARY.md because too much context was confusing them. I made 21 commits throughout the project and worked for about 6 hours (I was able to multi-task, so it wasn't 6 hours of hard effort). I spent about $14 on tokens via Zed and asked some questions via t3.chat ($8/month plan).

A final question: What open source license is good for these types of mini-projects? I took the path of least resistance and used MIT, but I observe that turingmachine.io uses BSD 3-Clause. I've heard of "MIT with Commons Clause;" what's the landscape surrounding these kind of license questions nowadays?

2 comments

| Group | Count | Purpose | |---|---|---| | `seek_delim_{clean,dirty}` | 2 | Pass entry: scan right to the next `0` delimiter between adjacent numbers. | | `cmpR_*`, `cmpL_*`, `cmpL_ret_*`, `cmpL_fwd_*` | 8 | Comparison: alternately mark units in the right (`B`) and left (`A`) numbers to compare their sizes. | | `chk_excess_*`, `scan_excess_*`, `mark_all_X_*` | 6 | Excess check: right number exhausted — see if unmarked `1`s remain on the left (meaning L > R, swap needed). | | `swap_*` | 7 | Swap: bubble each `X`-marked excess unit rightward across the `0` delimiter. | | `restore_\*` | 6 | Restore: convert `A`, `B`, `X` marks back to `1`s, then advance to the next pair. | | `rewind` / `done` | 2 | Rewind to start after a dirty pass, or halt. |