You may have heard of Alan Turing, the British mathematician that helped crack the German Engima device during WWII and who invented our current notion of how to tell if an AI is conscious like a human, but his first major contribution to mathematics and computer science, long before we had computers, was the invention of the Turing machine.
Turing machines are simple devices that are made out of some kind of paper tape, a pen, and a way to read, write, or erase what’s on the paper tape. They also can solve any problem that a computer today can handle. While to Turing they were entirely hypothetical, some people have tried to make physical machines like the video linked at the bottom of the article.
Turing didn’t call them “Turing machines”, though; he called them “a-machines”. He introduced them in a paper in 1936. The paper has a bit of a nondescript title: On computable numbers, with an application to the entscheidungproblem. That name doesn’t necessarily mean anything to us, but it meant a lot to other mathematicians at the time. In those days, mathematicians were very concerned about the “entscheidungproblem”, the decision problem.
The decision problem was about whether machines could potentially make the lives of mathematicians easier. They wanted to know whether it was possible to give a machine a logical statement and for the machine to run a program and decide if it is always true.
Turing came up with his a-machines to simulate the kind of device that might assist mathematicians. He was inspired by noting how computers, which back then meant people who carried out complex calculations with a pencil and paper, did their job.
All a computer needed to work was their pencil and paper and their knowledge of what calculation they were in the middle of. Other than that, they could take breaks, drink tea, talk to their coworkers and then come back to their work. What mattered was the “state” the calculation was in and the fact that they could look over their scratch paper and write on any part of it.
Similarly, a Turing machine has a set of steps it can be in, like the steps when you’re following directions. It also has its scratch paper, which is a really wide, but short, strip of paper split up into squares that each hold a single character: a letter or a number or a symbol. The Turing machine can read or write from just one square at a time but it can move the scratch paper strip, or tape, left or right.
What a Turing machine does in each step is to
- Read the current square on the tape and
- Based on the step it’s on
- write a new character into the square
- change to a different step
- move the tape left or right
- possibly stop the calculation
This is much simpler than how our current computers work, but surprisingly the Turing machine can do anything that our computer can. That doesn’t mean we can do it easily.
The tradeoff for having such a simple machine is that writing programs for it is pretty complicated. The processors in your computer or phone have built in instructions for how to do things like arithmetic or grabbing data from a particular place in memory.
A Turing machine has no notion of numbers or arithmetic or memory, just symbols. The input to the program is what’s written on the tape when the program starts. So the same way that we might start an addition problem with our scratch paper as
then if we wanted to run a Turing machine program for adding two numbers in binary, we might start our tape as
We won’t start with addition, though. Instead we’ll deal with a simpler program, where we’ll be checking to see if two numbers are the same. We’re going to simplify slightly by assuming that the two numbers are of equal length, with our initial tape looking like
Before we show the in-all-its-gory-details version of the algorithm, let’s discuss informally how you would do this. You’d check to see if all the symbols were the same in all positions. So, you’d probably start from the left side and compare each number, and if they’re all the same then the numbers are the same.
Now for the algorithm, written in full detail for how a Turing machine operates:
- Check the current symbol. If it’s a 1, cross it out, move to the right, and go to step 2. If it’s a 0, cross it out, move to the right and go to step 4. If it’s blank, stop the program because they’re not equal. If it’s a # then stop the program because the numbers are equal.
- Check the current symbol. If it is a #, move to right and go to step 3. If it’s a 1 or a 0, move the right and go back to step 2. If it’s blank, stop the program.
- Check the current symbol. If it’s crossed out, then move to the right and go back to step 3. If it’s blank, then stop the program. If it’s a 1, then cross it out, move to the left, and go to step 6. If it’s a 0, stop the program.
- Check the current symbol. If it is a #, move to the right and go to step 5. If it’s a 1 or a 0, move the right and go back to step 3. If it’s blank, stop the program.
- Check the current symbol. If it’s crossed out, then move to the right and go back to step 5. If it’s blank, then stop the program. If it’s a 0, then cross it out, move to the left, and go to step 6. If it’s a 1, stop the program.
- Check the current symbol. If it’s not a #, then move to the left and go back to step 6. If it is a #, move to the left and go to step 7.
- Check the current symbol. If it’s crossed out, move to the right and go to step 1. If it’s not crossed out, move to the left and go back to step 7.
In order for that algorithm to make sense, let’s pretend to be a Turing machine and evaluate this by hand. Start by drawing out the initial state of the tape on a piece of paper
And now write down the initial state of the tape, at the left most position, and the current step we’re on, which is step 1. So your paper should look something like
Now, we just follow the instructions above. Changing the step we’re on, the position of the tape reader, and the contents of the tape as needed. Here’s what your simulation should look like after one round
and after five rounds
From here, go on and see if you can write programs that perform the following calculations:
- Extend the program to determine equality so that it works with numbers of different lengths.
- Write a program that will double a number in binary.
- Write a program that will determine if a word is a palindrome.
- Write a program that can add two numbers in binary. This one can be tricky, but it’s just an extension of the previous programs. Here’s a hint that might help though: write the numbers on the tape from left-to-right instead of right-to-left e.g. the number 4 would be 001 instead of 100. That will make it much simpler.
If you’ve tried all of that, then it’s time to start thinking of how to do things like representing and storing data. How might you create or use something like variables in a Turing machine? How might you store arrays of data? How would you represent interactive input and output?
After all, there’s nothing your computer can do that your pen & paper Turing machine can’t.
A video of a working Turing machine. The creator describes the physical machinery more than how it’s programmed.
On computable numbers, with an application to the entscheidungproblem
Turing’s original paper. It’s fairly technical but worth skimming.
Turing Machine on a Raspberry Pi
If you’re more interested in hardware than pen & paper, here’s a guide on building a Turing machine simulator in hardware with a row of LEDs representing the tape