How the Turing Machine interactive simulator can help you understand algorithmsLazar GugletaBlockedUnblockFollowFollowingFeb 21Let’s remind ourselves where zeroes and ones all began with a new approach and program that simulates the Turing machine.
Many of you reading this might know what I am talking about.
But for those of you that do not, I am going to explain what a Turing machine is and how it works with a simulator.
What is the Turing machine?When you first see a Turing machine, at a first sight there is not much that tells you how to operate it.
But if you look closely, there are many components that bring this wonderful machine to life.
A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a tape according to a transition table.
That is a lot of complicated words, but here’s a simple explanation: the Turing machine is a machine that can simulate any computer algorithm no matter what level complexity it is.
Nowadays, the Turing machine is used to help people gain a better understanding of algorithms and how a computer works, which is why this simulator was created.
About the simulatorMy first experience with this simulator was when I had to use it for college, at TU Graz, to practice using the Turing machine.
At first, it was confusing — so do not give up at the beginning.
The simulator is very detailed when it comes to its options.
You are able to import/export files from the machine, and the format it uses is JSON (most commonly), but you can use FOSWIKI as the output type.
Why would you want to use this simulator?This simulator is primarily made for those who are beginners and are just now learning how the Turing machine works.
Of course, this software can also be used for teaching and making simple programs to train your brain (examples are at the end of the article).
Now let’s see what it looks like and how to use the simulator.
How to operate the Turing machine simulatorHere is the link to the website.
Once you open it, it looks like this:Now I would like to explain every part of this simulation.
Going from top to bottom: first, we see a track with empty spaces that are meant to be filled with zeroes, ones and other signs.
There is an animation checkbox which enables you to see the very smooth moving of the track when the machine is executing your code.
Import or export buttons are used for importing or exporting your code.
File function is still in beta, but it is supposed to do the same thing as import-export — it just writes to the files directly.
But you should stick with import and export which are much stable for now.
Now a very important part of this program are functions: back, continue, slower, reset, run and faster.
Let’s go over them one by one:1.
Back and continueThese are used for taking 1 or multiple steps forward or backward.
Once we load the code in the machine it will get clearer.
2.
Slower and fasterOnly for controlling the speed of the animation when the track starts moving.
3.
RunIf you do not want to manually go back and continue step by step, you can just press run in order to execute your code for the machine.
That was all for the track part, now let’s move on to the transition table to program our machine.
Programming the machineThe transition table is the most important part of this simulator, because it is where we actually develop the code and states for the machine.
In order to explain it more clearly, I would love to introduce some new exercises, which are supposed to make it easier for you.
Check for equal (example)In this example, as its name tells us, we are going to check for the equality of two numbers.
RulesTwo binary numbers are being checked.
There must be an equal sign which separates them.
Solution and explanationHere is my transition table (see below), which has 7 states and 6 different values for these states to react to.
I will just briefly explain my approach to solving this simple problem.
The logic for the solutionI went through both numbers, and compared each digit one by one.
If these are the same in the same position, we go further; if not, the program stops and the final state goes to notEqual.
Once every digit has been checked the program ends in the final state is named Equal.
Also, just so you understand better, every time the digits are the same, 1 is replaced by x and 0 is replaced with y.
Let’s see how some of the states work:Transition table and data for example “Check for equal”StartThis state is, as its name tells us, the starting point of the program.
The Turing machine goes from right to left, and the starting point in the tape you can see in the Data section.
It is marked with asterisks (* *).
Whatever is in-between them is our starting point.
In this example, it is an empty space which is written as _ (underscore).
When the program is starting we have to make sure to tell it what to do in every possible situation.
In our tape example, first to come is an empty space.
Since our state is Start we replace _ with a _, move to the right, and our new state is Start.
Next comes zero, and at that moment the Start state replaces zero with the character “y”, moves the pointer of the tape to the right, and goes into “Check0” state.
I think at this point you get it how it works, so I will just briefly explain what every state does, not to waste your time too much.
Check0Zero was previously registered as a number to be checked with this state, so we move to the right until we find a sign “=”, which tells us that another number is about to be checked for zeroes.
Check0=0Comes right after the equals sign in the second number to search for zeroes.
If the zero is found at the same position in the first number, it is replaced with a “y” and is moving to the left to check the rest of the number.
GoBackA simple state to move the pointer back at the beginning and search for a new number to check if it matches.
Check1/Check1=1The same principle as for the zero.
CheckForBiggerRightThis state is used for an extra check to make sure there is no number on the right of the second number, because it may happen that the whole first number matches the beginning of the second one.
Complete solutionHere is the already working program (password: TuringMachine), which I wrote when we had the assignment for it.
If you want to check out for yourself you can just simply copy the code and import it in your machine.
Extra assignmentsIf you want to try to program the machine without too many explanations, try these assignments, which I also have solutions for (but first, try on your own).
Addition — add two binary numbers together“+” sign must be between themSolutionDivision — divide a binary number with 2 and print it outSolutionConclusionYou can use this software to help you learn how the Turing machine works.
Please do not sell the program or misuse it :)Hope you learned something today!If you liked this story check my profile out and my latest story on Big O notation.
Thanks for reading.
.