This is the sixth part in my multi-part series on computing. In the previous parts, we learned about Boolean logic, the language computers think in. We then learned how to implement this logic electronically. And finally, we learned how to make computer memory, so that computers can record results of calculations.

Now before we conclude the series, we’re going to take a quick detour into computational theory and the Turing machine.

Alan Turing’s Machine of the Mind

In 1936, mathematician, WWII codebreaker, and all around awesome guy Alan Turing wanted to investigate a problem in formal logic. Specifically, he wanted to find the answer to a question first posed by David Hilbert. Simplistically, the problem is this:

We know from Godel’s incompleteness theorems that some mathematical questions simply do not have answers. But Godel opens up a Hydra’s den. Are there some mathematical questions that have answers… but answers… but answers that it is impossible for a human being or machine to discover, even in principle?

To answer this question, Turing devised a theoretical machine designed to compute the answer to any question one can pose in mathematics. You’ve probably heard of it, even if you don’t know what it does. This is the Turing machine.

To Build a Turing Machine

A Turing machine is a pretty simple device, but it sounds complicated when you describe it. So I think the best way to understand what’s going on is by example. So let’s try a little experiment where we play the role of the “brains” of a Turing machine. I’m going to give you three things and you’re going to manipulate them to form a Turing machine.

First, I’m giving you a tape, say a long ribbon of paper, partitioned into little blocks or cells. With nothing written on it, it looks something like this:

(In principle the tape could be infinitely long, but we’ll ignore that.)

Initially, the tape WILL have some symbols written on it. It’ll look like this:

But let’s say I wrote on the tape in pencil. This means you can erase any symbol I’ve written on it and replace it with something else. Just make sure you use pencil!

I’m only going to allow you to write one symbol in each of the cells on the tape. And I’m going to restrict what you can write. Here are the symbols you can use: “1”, ” “, “-“,  and “=”, where ” ” represents a blank space.

Next I’m going to give you a spinner like the one you might get for a game of Twister. Ours will have an arrow that can point at one of four colors: Red (R), Green (G), Blue (B), and Yellow (Y).

You won’t just randomly spin the arrow. You’ll move the arrow to keep track of a color. Let’s start the spinner pointing to red, as shown below.

Finally, I give you the following table. The table tells you what to do based on the symbol you read on the tape and the color of the spinner. Here’s the table:

Let’s work through it.

Now, just start by looking at the symbol in the leftmost cell of the tape, as shown below.

The symbol is a “1” and the spinner is pointing to “Red.” If you look at your table, you see it tells you to do nothing and just look at the symbol in the cell one to the right. If you do, you see that this symbol is also a “1” and we’re just supposed to move right again.

This process repeats for a while. The instruction table doesn’t tell us to do anything different until we reach the “=” sign shown below.

If we look at our instruction set, it tells us to “erase the symbol and replace it with a space” and then “move one cell to the left and change the spinner to point to Blue.” So let’s do that. After we do, the Turing machine looks like this.

Now the rules tell us to replace this symbol with an “=” sign, move one cell to the left, and change our spinner to point to “Green.” Let’s do that. The results are shown below.

Now the rules tell us to move once cell to the left and change the spinner to “Yellow.”T he results are shown below.

Now the rules tell us to erase the “1”, replace it with a blank space, move to the right, and change the spinner to red, as shown below.

Well, we know what to do when the spinner points to “Red.” We move right! This continues until we get to the equals sign, as shown below.

And we erase the equals sign, as shown below…

But now our spinner is pointing to “Green” and we’re looking at a “-” sign. The instructions tell us we’re done!

 So… What?

So what have we done, exactly? Well, our tape started with an expression that looked roughly like

   

and we ended up with an expression that looked roughly like

   

In other words, we used a simple tally mark system to take the number “3” and subtract “1!” This sounds simplistic, but it’s not. We wrote down a set of rules so that given any number of tallies left of the equals sign and any number of tallies right of the equals sign, we can subtract the tallies on the right from the tallies on the left. And we can do so without any thinking at all, just by looking at the rules in our table.

So What’s a Turing Machine?

A Turing machine is only a little bit more general than what we just described. It has three parts:

1. A ticker tape consisting of cells that can be written in. We select an alphabet of symbols we’re allowed to write. In our simplistic example, our alphabet consisted of “1”, ” “, “-“, and “=” but it could easily describe more symbols. For example, you could easily use the real alphabet or every character available in unicode. Whatever you like.
2. A “head” that can read from the tape and write to it. The head also has a finite number of “states” or modes. You can think of these the same way you think of the modes available to your printer at home. A printer probably has a “scan” mode, a “print” mode, and mavbe a “fax” mode. These determine what the printer does given some input. Similarly, the state of the head determines what it does when it reads a symbol. In our example, the states were the four colors: “Red,” “Green,” “Blue,” and “Yellow.”
3. A rules table. The table tells the head what to do when it reads a symbol off of the tape given the state it’s currently in.

Turing postulated that if there is a problem in mathematics that you can find the answer to, you can build a Turing machine that can find the answer. We currently believe this to be true, though the answer isn’t really known. (Aside: this hypothesis is called the Church-Turing Thesis.)

But, more relevantly (for us anyway), a Turing machine is a model of a single-purpose computer. Next time I’ll explain how and explain how to get from this to a fully programmable computer.

Further Reading

Here are some resources on Turing machines.

• The Wikipedia article on Turing machines is, of course, a good place to start.
• Mark C. Chu-Carroll has a very nice introductory article on Turing machines, from which I stole my example machine. You can find it here.
• I-Programmer also has a nice article on Turing machines. It’s clearly meant for programmers and software engineers, but a layperson should be able to follow it. Find it here.
• You can download a Turing machine emulator for your android phone here.
• Want to learn how to build a Turing machine with a Raspberry Pi? Learn how here.
• Google made a doodle Turing machine for Turing’s birthday. It’s archived here.
• Want to build a Turing machine out of legos? You can! Find out more here.

Related Reading

This is the sixth article in a multi-part series on computing. These are the other parts:

• In this article, I describe the basics of Boolean logic, starting with truth tables.
• In this article, I describe how to make composite logical statements using Boolean logic.
• In this article, I introduce the triode vacuum tube and describe how it works.
• In this article, I show how to use triodes to make logic gates.
• In this article, I explain how to build computer memory.