Insertion sort using Turing Machine
Possibly you are here because you are taking automata class and trying to understand how a basic machine works. So buckle up, we are going to take a look the Turing Machine and how to use it in an algorithym for sorting.
What is Turing Machine?
TM(Turig Machine) is an abstract machine, it has a infinite tape and 7-tuple: states that decide move(Q), blank symbol in the areas that doesnt have an input,T tape alphabet that tape accept, ∑ alpabet inputs, δ funtion that moves and change in the tape(Q x T), q0 initial state and F set of final states. I will be explaining the tuples little bit later. TM was invented by Alan Turing in 1936, he called it a-machine as automatic machine.
So what is an abstract machine? It’s a theoretical model of a computer used in automata theory. Oops,what is automata theory by the way? Automata theory is a computer science branch that designs abstract computing devices that follows predetermined sequence of operations. TM is a FSM(finite state machine).
Let’s turn back to TM. What is infinite tape? Think it like an infinite lenght of paper that has only one line to write. You can change what is written on the paper. It has only one line because think it like you are writting about same subject in same paper. There are other types of TM that has multiple tapes but it has the same rule, one subject for one tape; example of this is simulating tic tac toe using tm, there you have tapes for player a, player b and the board so there is 3 tape. We don’t need that for this algorithym.
Now let’s look at 7-tupple of TM:
· Q the set of states; like go left if input is 1 ,is a state
· T is the tape alphabet that tape accepts. It can be numbers, symbols,alphabet like T={0,1,X,B}
· ∑ is the input alphabet ∑={0,1}
· δ The transaction function Q x T → { Q x T } x {L,R} here L,R means left or right to move in tape, T is the alphabet and Q is the state that choose to move left of right by current T.
· q0 is the initial state
· F is the set of final states
· B blank symbol
Why I choose to use insertion sort?
I was thinking between bubble sort, selction sort and insertion sort because these three are the best methods for using TM. They have averge O(n²) but selection sort’s best case is O(n²) too so I eleminated it.
TM design for sorting
Now let’s look at our TM design for insertion sort. It’s actually a comparison TM design.
In easy words we will change each num’s ones to “X” one by one, when one num is finished other num still has ones that num is bigger. Lets put it together.
We have an infinite tape. We put two numbers made from “1”s (ex. For 8, 8times 1) and between our two numbers we put “0”. Then we start our comparison, starting from first num’s ones we change one 1 to “X” then we go right in the tape and find “0” to find where our second num starts. We change second num’s first “1” to “X” too. Then go left and find 0 to know we will be back to first num. Then go left till we find “X”, so we now where we left. Go right change first “1” to an “X” and go right in the tape find “0” to find where our second num starts, then again go right to find “1” and change it to “X”, continue that circle till in first num finishes and you came to “0” or second num finishes and you came to B(black symbol in the tape) or both.
In the end if you found “0” in the tape first num> second num, if you found “B” in the tape second num> first num and if you found both “0” and “B” first num=second num.
Our tupples for this design:
· Q={q0,q1,q2,q3,q4,q5}
· T={0,1,X,B}
· ∑={0,1}
· δ: Q x T → { Q x T } x {L,R}
· q0∈Q
· F ∈ Q : q2, q5
Now let’s look at my code.
First thing first I made a class for TM. It has some properties. TMBand for TM tape, A for first number, B for second number. IndexforSeperation for make finding “0” easy each time but you can add if sentences to find “0” instead of using this property. Lastly I had to determine TMBand as new list in constructor.
Next, still in TMclass, I added a compare method for determining and manipulating TM tape.
As I took TM as a list(I though it was easier to fit an infinite tape,I can just move it), I added “B”(our blank symbol) to the tape. Than I added our first num to compare, then “0” to find i easy(as I said you can basicly write if sentences to find our “0” too) and I fixed our seperation index to the “0”. Then continue adding, first B as second number , and “B” for blank. We can assume after these “B”s tape goes infinite filled with “B”s.
Last thing for compare method we have to add our transaction function without final set states. So this is the part we change “1”s with “X”s. To start, from i=1(at list[0] we have “B”) changing list[i]=”X”; then going to our “0” and againg going as i, we find our second num’s “1” and change it to “X”. This is the part we can add if sentences. We can put while and look for “0” then if we are going right again with while we need to search for “1” and change it to “X”. If we were going left after finding “0”, this time we would be looking for first “X” with while. After finding we would move right and change the first “1” .
To be able to change insertion sort to any other sorting type, I used an abstract class for sort.
Here as you see the abstract sort class has some properties. An integer array to hold array from form, c for array lenght, sum for our final sorted string and an abstract method sorting to turn a tuple that holds our sum from sorting and TMBand sequence for logging.
There is a method for converting our nums to tape inputs. It returns nums as made from “1”s.
Lastly in sort class I wrote a function that convert given array to TM tape input array so it is easier to choose from.
Our third class is insertion sort. This class inherited from our sort class. It doesn’t have a property but it has to override the abstract method Sorting. Here lw for listview(to add TM tape outputs) and str is our array in tape input type.
Here is the our real insertion sort method. As simple as I can explain insertion sort is an algorithym that checks neighbors for sorting. Here I determine an arra for our TM tape log and added it onlist to return in our tuple.
Then we need to check which final state is out. For this in if sentence we check for if before “0” is “X” and before B is “1” or not “X”
In that case our second num is bigger but since j-1 is the second num we have to change their values.
On else if sentence we check for duplicates if “X”s from first num reached the “0” and “X”s from second num reached the “B” they are duplicates. We have to increase j in order to keep up.
Then we convert our array to string and as a tuple return values.
In the form.cs we make our new sorting object. Then taking our input(array) looking for if last key is blank and if it is, we remove it. Then we split our array by blanks. Then we define a tuple for our sorting returns. Item 2 is our logs, for each log we add them in listview. And as output our sum is Item 1.
