So I've got a compulsory exercise set in my "Modelling of Computing" course. It's about turing machines and state machines and logic circuits and computability and that sort of stuff. The book used is
So, sort any string consisting of a's, b's and c's alphabetically; "cba" to "abc". Pretty simple stuff.
Now, the thing is, writing Turing machines in the form of state transitions gets kinda... messy. I hit 30 transition functions and lost completely track of where I was at. So, I figured I'd do this the good old fashioned way: test driven development! Yeah!
Now, to actually test a Turing machine, I need to have an actual Turing machine implementation. So I did that. Because to solve a simple problem, first solve a harder problem. This is the mantra! So now I can write Turing machines through TDD by testing against the expected output tape state. Aw yeah. The machines I can build don't actually have explicit accepting halting states - ALL halting states are accepting. So if they're used for language recognition, they can give positive answers ("the input string is in the language") by halting, but not negative ones.
. Not sure
/*
* bubbleSort is a turing machine with starting state R. TM.RIGHT is the "go right" command, TM.LEFT is the "go left" command, and TM.EMPTY is an empty tape bit.
* .setTransition("X", "a", "Y", b) means that in state X, when reading a, go to state Y and write b. If b is LEFT, go left instead. If b is RIGHT, go right instead.
*/
// R: "Run" (normal)
bubbleSort.setTransition("R", "a", "R", TM.RIGHT);
bubbleSort.setTransition("R", "b", "B", TM.RIGHT);
bubbleSort.setTransition("R", "c", "C", TM.RIGHT);
// B: "the last character read was b"
bubbleSort.setTransition("B", "c", "C", TM.RIGHT);
bubbleSort.setTransition("B", "b", "B", TM.RIGHT);
bubbleSort.setTransition("B", "a", "Ba", "b");
bubbleSort.setTransition("Ba", "b", "Wa", TM.LEFT);
// C: "the last character read was c"
bubbleSort.setTransition("C", "c", "C", TM.RIGHT);
bubbleSort.setTransition("C", "b", "Cb", "c");
bubbleSort.setTransition("Cb", "c", "Wb", TM.LEFT);
bubbleSort.setTransition("C", "a", "Ca", "c");
bubbleSort.setTransition("Ca", "c", "Wa", TM.LEFT);
// Wx: "Write x"
bubbleSort.setTransition("Wa", "b", "R", "a");
bubbleSort.setTransition("Wa", "c", "R", "a");
bubbleSort.setTransition("Wb", "c", "R", "b");
// ML: "Mark last"
bubbleSort.setTransition("R", TM.EMPTY, "ML", TM.LEFT);
bubbleSort.setTransition("R", "a'", "ML", TM.LEFT);
bubbleSort.setTransition("R", "b'", "ML", TM.LEFT);
bubbleSort.setTransition("R", "c'", "ML", TM.LEFT);
bubbleSort.setTransition("B", TM.EMPTY, "ML", TM.LEFT);
bubbleSort.setTransition("B", "b'", "ML", TM.LEFT);
bubbleSort.setTransition("B", "c'", "ML", TM.LEFT);
bubbleSort.setTransition("C", TM.EMPTY, "ML", TM.LEFT);
bubbleSort.setTransition("C", "c'", "ML", TM.LEFT);
// RTS: "Return to start"
bubbleSort.setTransition("ML", "a", "RTS", "a'");
bubbleSort.setTransition("ML", "b", "RTS", "b'");
bubbleSort.setTransition("ML", "c", "RTS", "c'");
bubbleSort.setTransition("RTS", "a", "RTS", TM.LEFT);
bubbleSort.setTransition("RTS", "a'", "RTS", TM.LEFT);
bubbleSort.setTransition("RTS", "b", "RTS", TM.LEFT);
bubbleSort.setTransition("RTS", "b'", "RTS", TM.LEFT);
bubbleSort.setTransition("RTS", "c", "RTS", TM.LEFT);
bubbleSort.setTransition("RTS", "c'", "RTS", TM.LEFT);
bubbleSort.setTransition("RTS", TM.EMPTY, "R", TM.RIGHT);
// F: "Finished" (clean up now
bubbleSort.setTransition("R", "a'", "F", "a");
bubbleSort.setTransition("R", "b'", "F", "b");
bubbleSort.setTransition("R", "c'", "F", "c");
bubbleSort.setTransition("F", "a'", "F", "a");
bubbleSort.setTransition("F", "a", "F", TM.RIGHT);
bubbleSort.setTransition("F", "b'", "F", "b");
bubbleSort.setTransition("F", "b", "F", TM.RIGHT);
bubbleSort.setTransition("F", "c'", "F", "c");
bubbleSort.setTransition("F", "c", "F", TM.RIGHT);
TL;DR: Programming at a university miiiight just have driven me insane.