Turing Machines for Dummies

How is a Turing Machine different from a “regular” Computer

You have at some point have been introduced to Turing Machines as the first theoretical description of a computer. However if you were like me, when first introduced to a Turing machine the explanation did not make a lot of sense.

One of the problems with understanding Turing machines is that the explanation is provided in a vacuum. There is no contrasting with regular computers and so the whole thing seems utterly alien and weird.

I am going to try to explain a Turing computer by comparing its various parts to that of a “regular” computer, following what we call the von Neumann architecture.

Practical Example of a Turing Machine

One way to get an initial impression of what an actual Turing machine would look like, is to look at this wooden mechanical Turing machine.

Turing’s explanation of his machine was meant as a theoretical construct and not really something to implement physically. However it seems to have been inspired by the kind of hardware that existed at the time.

In this time electronic memory that could store whole programs did not exist and was not something people where familiar with. However people where used to representing data on punched paper tapes. Teletype machines, stock tickers, telegraphs etc used punched tape to store and load data.

The Tape

Thus Turing’s explanation that his machine would read data from a tape made sense in his time. In the video, the tape is represented as a belt with wooden pegs on. In a theoretical Turing machine each cell on the tape could contain any symbol belonging to some predefined alphabet.

Machine Alphabet

“Predefined alphabet?” What a kind of gobbledygook is this? This is to account for the fact that theoretically speaking the machine can have many different ways of representing data. E.g. the computer you normally work with works with 1s and 0s. So the alphabet is just 0 and 1. An alphabet in this context just means a set of symbols. Every cell on the tape has to be a letter from this alphabet.

The wooden Turing machine has an alphabet of b, 0 and 1. Each of these "letters" are represented by 3 different configurations of the wooden pegs.

Charles Babbage’s Difference Engine in contrast was not a binary digital computer. Instead it worked directly with decimal numbers. Its alphabet was thus the digits 0, 1, 2, 3, 4, 5, 6, 7 , 8 and 9. Each of these digits (or characters) in the alphabet of the machine was represented by the position of a gear with ten teeth. In a modern digital computer 1 and 0 is represented by two different voltage levels.

However keep in mind that what a cell is highly theoretical. Thus far we have thought about it as individual bits or digits. However it could also be a whole byte. The point is that a cell is read as one unit and handled as a unit.

Reading and Moving the Tape

If you watch the video you can see that there is a head reading the tape, by checking where the wooden pegs are placed. Depending on what the Turing Machine reads it can move left or right on the tape.

How the data that is read is dealt with is determined by the metal pegs on the square board on the left side of the machine, called the “Configuration Table.”

Comparison with a von Neumann Machine

In a von Neumann machine you got a program stored in random access memory. The CPU in the computer reads on instruction from memory and executes it. An instruction could be things like:

1. Read a byte from memory location 3 into a CPU register 4.
2. Add bytes in register 3 and 4 as if they where integer numbers, and store result in register 3.
3. Write 2 bytes in register 5 inside the CPU to memory location 6.
4. Multiply two numbers in two different registers, alternatively subtract or divide.
5. Change program counter (jump) to start executing code at some different location in memory.
6. Conditional jump. Jump to a particular instruction in memory depending on the result of previous calculation.

When looking at a description of a Turing machine, it is very hard to see where similar kinds of things are going on. A Turing machine does not have random access memory with data and instructions. Both are kept separate.

Reading and Writing Data

The tape is where you read and write data. It is not where you get the program instructions. And it is not random access memory. In a von Neumann machine, you can say write this number to memory at location 4. In a Turing machine you can only write to the current position. There are no other choices.

Executing a Program

In a von Neumann machine the program lay in memory in as a collection of instructions which are read in sequence. The program in a Turing machine is not like that. It is not read one instruction at a time. It is not organized as a sequence of instructions.

Instead it is a bit like event based programming. When you program a GUI, you attach code to events like “button A got pressed” or “slider C got dragged.” A Turing machine is a bit similar in that the Configuration Table says what should happen for a given state when a particular symbol is read on the current cell of the input/output tape.

The Turing Machine has some sort of memory cell which keeps track of its current state. The state can be simply a number or a letter. The current state combined with what is read on the tape forms the input to the “program” on the configuration table.

The Turing machine is what we call a final state machine FSM.

Above is a diagram of such a machine. Each circle with letters such as A, B, C and H represent states the machine can be in. The arrows represent possible state transitions. For instance C has arrows pointing to B and H. Which means it is possible to transition from state C to state B or H. However it is not possible to transition from C to A.

The configuration table basically describes such a diagram. In a final state machine diagram we label arrows with events that trigger a transition from the beginning of the arrow the end of the arrow. For some types of final state machines such as the Turing machine and Mealy machine we add a slash / to indicate the actions to perform when such a transition happens.

Let me explain how this works with an example. Look at the diagram at the arrows going out from state B:

• 1/1,R the arrow going back onto B.
• 0/1,L arrow going from B to A.

1/1,R means that when we read a 1 on the tape, we transition to B and perform the actions 1,R. 1 means print a 1 symbol to the current cell. After that we do the next instruction, which is move tape to the Right.

0/1,L is similar. When a 0 is read on the tap, make transition to next state as indicated on diagram. Then we print a 1, before moving Left on the tape.

How Does it Do Arithmetic?

You have probably noticed that no specific instructions such as add, subtract, multiply etc is defined on a Turing Machine. A Turing machine is far more generic than that.

You would have to design a state transition diagram and alphabet that facilitates addition of input data on tape. Alternatively we can imagine creating a sort of calculator, where the input tape not only contains the numbers to perform arithmetic on, but also the operation to perform.

Subtraction Example

Here is an example of a Turing Machine just made for subtraction.

The state transitions are written such that what is on the left side of / is what you have read on the tape. The right side are the actions to perform. 1/0,R. Mean you read a 1. Then you write a 0 and more Right.

It is highly inefficient, but it gets the job done. Remember the idea of a Turing machine is not to be able to compute efficiently, but to be able to compute anything computable with as simple machine as possible.

So to make this simple, we are not using decimal numbers, we are not even using binary numbers! No, we are using unary numbers. So you got to count 1s. The number 3 is written as 111. The number 4 is written as 1111 and so on. This will be terribly inefficient when dealing with say thousands, but it doesn’t matter because a Turing machine is a mathematical construct with an infinitely long tape to store information on.

So my alphabet is made up of 1, 0 and c. We use 1 to represent ones and 0 to represent noting. So that 110, 011 and 101 all mean just two. c is used to separate the two numbers being subtracted. Thus 111c1111 means 4 - 3. Alternatively you can think of it as 3 - 4 in which case the number of 1’s represent a negative number.

I will write step by step how this Turing machine will run. At each step I will write, what state the machine is in at the beginning of the step and the edge that will be followed to get to the next state.

Here is an example:

A  →111c1111  1/0,R

This says we are in state A and the tape looks like 111c1111 and the edge which transitions to B in this case is labeled with 1/0,R, which means reading a 1 triggers this transition and it causes the actions 0,R to be performed. These actions are write 0 and move right R on the tape. The → says where on the tape we are at. What the current symbol is.

So here are the steps:

A  →111c1111  1/0,R
B  0→11c1111  1/1,R
B  01→1c1111  1/1,R
B  011→c1111  c/c,R
C  011c→1111  1/0,L
D  011→c0111  c/c,L
E  01→1c0111  1/1,L
E  0→11c0111  1/1,L
E  →011c0111  0/0,R
A  0→11c0111  1/0,R
B  00→1c0111  1/1,R
B  000→c0111  c/c,R
C  000c→0111  0/0,R
C  000c0→111  1/0,L
D  000c→0011  0/0,L

This continues for a while. If you follow the pattern, what you may notice is going on is that the Turing machine is ping-ponging back and forth on each side of the c symbol. Each time it visits one side it erases one 1, before moving to the other side and erasing as 1 there by replacing it with a 0.

Since we are always removing equal number of 1s on each side, we are effectively performing a step by step subtraction. Eventually when there are no more 1s on one side, the machine will terminate. At that point the number of 1s left on one side represents the computational result.

One could design Turing machines operating on binary, decimal or some other number system, but that would require a dramatically more complicated state diagram. From an education perspective that would be harder to explain.

You can watch this youtube video of a physical Turing machine performing subtraction using this method.

Summary

I am trying to structure this summary around my previous misconceptions about Turing machines which others hopefully can relate to.

1. The Turing machine tape is not where the data and instructions are read. You cannot compare it to the program memory. The “program code” if you will can be thought of as existing in the configuration table. This table is visualized as the state diagram with circles connected with arrows.
2. Input data comes from the tape. However this is also where the Turing machine writes its output.
3. No the Turing machine is not a binary computer. It can operate on any number of symbols, not just 0 and 1. You define which symbols are allowed by defining its alphabet.

It is not meant to be efficient, just to be simple.