GitHub - purplejacket/bubble_sort_on_tm: A Turing Machine that will perform a bubble sort on the tape input; compatible with turingmachine.io yaml format. Two variants of the Turing Machine are provided.

Bubble Sort on a Turing Machine

A Turing Machine that sorts arrays using bubble sort — implemented as a YAML state-transition table compatible with turingmachine.io, plus a Python emulator to run and verify it locally.

Two variants are provided:

Both YAML files can be pasted directly into turingmachine.io to watch the sort happen step by step.

Here's the unary bubble sort in mid-flight:

Quick start

# Run the decimal bubble sort and see the result
make run-decimal

# Run the unary bubble sort
make run-unary

# Run the full test suite (135 tests)
make test

# See all available targets
make help

Requirements

• Python 3.10+
• PyYAML (pip install pyyaml)

No other dependencies. The test suite uses the standard-library unittest module — no pytest required (though it works with pytest too if you have it).

Project structure

.
├── bubble_sort.yaml            # Decimal digit TM (25 states, alphabet 1-7)
├── bubble_sort_unary.yaml      # Unary-encoded TM (~30 states)
├── emulator.py                 # Python TM emulator (CLI + library)
├── generate_yaml.py            # Generates bubble_sort.yaml programmatically
├── test_bubble_sort.py         # Original standalone test runner (decimal)
├── Makefile                    # Build/test/run targets
├── tests/
│   ├── helpers.py              # Shared test utilities (unary encode/decode, etc.)
│   ├── test_emulator.py        # Emulator unit tests + fixture-based tests
│   ├── test_bubble_sort_decimal.py   # Tests for bubble_sort.yaml & generator
│   ├── test_bubble_sort_unary.py     # Tests for bubble_sort_unary.yaml
│   └── fixtures/               # Example TMs for emulator testing
│       ├── anbncn.yaml         #   aⁿbⁿcⁿ language recognizer
│       ├── busy_beaver4.yaml   #   4-state busy beaver (107 steps, 13 ones)
│       └── div3.yaml           #   Binary divisibility-by-3 checker
├── SPECIFICATION.md            # Detailed design document
├── INITIAL_IDEAS.md            # Early design conversation notes
└── EXAMPLES_YAML.md            # Example TMs from turingmachine.io

How it works

Decimal version (bubble_sort.yaml)

Each number occupies a single tape cell (digits 1 through 7). Blank cells (' ') mark both ends of the data.

The machine performs repeated left-to-right passes. On each pass it reads adjacent pairs, compares them via the current state (which "remembers" the left element's value), and swaps if out of order. A pass that makes no swaps means the array is sorted — the machine halts.

25 states in four groups:

For the spec input 327154, the machine sorts to 123457 in 63 steps.

Unary version (bubble_sort_unary.yaml)

Numbers are encoded in unary — n is represented as n consecutive 1 characters — separated by 0 delimiters. For example, [3, 2, 1] becomes 11101101. The machine expects positive integers; zero is not representable in this encoding.

Since numbers aren't single symbols anymore, comparison requires a marking-based approach: alternately mark one unit in the right number (B) and one in the left (A). If the right number runs out first and unmarked 1s remain on the left, then left > right and a swap is needed. Swapping moves the "excess" units (marked X) across the 0 delimiter.

31 states in six groups:

Most groups carry clean/dirty variants to track whether a swap has occurred during the current pass (same idea as the decimal version). The swap states don't need variants — a swap always means the pass is dirty.

For the spec input [3, 2, 7, 1, 5, 4], the machine sorts to [1, 2, 3, 4, 5, 7] in 1424 steps.

The emulator

emulator.py is a general-purpose Turing Machine emulator compatible with the turingmachine.io YAML format. It handles:

• Flow-sequence keys (e.g. [a, b, c]: R)
• Shorthand transitions (R, L)
• Dict transitions ({write: sym, R: next_state})
• Any blank symbol
• Halt states (states with no transitions)

Usage

# Default: show summary
python3 emulator.py bubble_sort.yaml

# Verbose trace — print every transition
python3 emulator.py bubble_sort.yaml -v

# Limit to N steps (exits with code 1 if the machine doesn't halt)
python3 emulator.py bubble_sort.yaml -n 200

# Run any compatible YAML
python3 emulator.py tests/fixtures/busy_beaver4.yaml

As a library

from emulator import TuringMachine, preprocess_yaml
import yaml

with open("bubble_sort.yaml") as f:
    config = yaml.safe_load(preprocess_yaml(f.read()))

tm = TuringMachine(config)
while not tm.halted():
    tm.step()

print(tm.tape_contents())  # "123457"
print(tm.steps)            # 63

Testing

The test suite covers:

• Decimal TM — spec input, all 49 two-digit pairs, all 210 three-element permutations, four-element permutations, duplicates, seven-digit cases, already-sorted and reversed inputs, static YAML vs. generator equivalence.
• Unary TM — spec input, single elements, all small two/three/four-element permutations, duplicates, equal elements, multiset preservation, large values.
• Emulator — busy beaver (107 steps / 13 ones), div3 checker (systematic up to 60), aⁿbⁿcⁿ recognizer, YAML preprocessing, transition parsing, TuringMachine class unit tests, step limits, edge cases.

make test               # 135 tests, ~30 seconds
make test-verbose       # Same, with per-test output
make test-decimal       # Only decimal TM tests
make test-unary         # Only unary TM tests
make test-emulator      # Only emulator tests
make test-legacy        # Original test_bubble_sort.py runner (10 tests)
make test-all           # Both unittest suite and legacy runner

The YAML generator

generate_yaml.py programmatically produces a bubble_sort.yaml for any digit string:

# Default (327154)
python3 generate_yaml.py > bubble_sort.yaml

# Custom input
python3 generate_yaml.py 54321 > bubble_sort.yaml

# Via Makefile
make generate INPUT=7654321

The generated machine always has exactly 25 states and handles the full 1–7 digit alphabet regardless of which digits appear in the input.

Visualizing on turingmachine.io

1. Open turingmachine.io
2. Copy the contents of bubble_sort.yaml (or bubble_sort_unary.yaml)
3. Paste into the YAML editor
4. Click Load then Run

The decimal version is particularly nice to watch — you can see the larger digits "bubble" rightward on each pass.

License

This project is licensed under the MIT License.