Turing’s Machine: A Simple Example

blue-square-quilt-opus-lxxi

I

The Turing Machine is a theoretical device first described by the British mathematician Alan Turing 1. It is a computing machine that manipulates symbols on a strip of tape. The tape is divided into cells which contain a predefined set of symbols, and is assumed to be infinite in length.

The machine can only perform a finite number of operations; in the example we’ll discuss here, it can read, write, erase, and move one cell to the left or right.

Strangely enough, this simple machine is powerful enough to compute any function that is capable of being computed (Ibid.).

Whatever computations the machine performs must be defined in terms of those operations. We’ll examine two basic operations, addition and subtraction – how they’re defined symbolically, as well as how they’re computed by the machine itself.

We begin with a strip of tape. On it is printed a representation of the two numbers we want to add. “Filled” cells are represented by the number 1. “Blank” cells are represented by 0. Here’s how we would write 4 followed by 3:

| 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

The easiest way to visualize adding the two numbers is to shift the number on the right one space to the left. However, even that simple concept is too complicated for the machine to understand. Therefore we must translate our wishes into a series of finite commands which will be executed in sequence. One way of defining an addition function is to use an instruction table like the following:

SYMBOL/STATE 1 0
0 RIGHT/STATE 0 RIGHT/STATE 1
1 RIGHT/STATE 1 LEFT/ERASE/STOP

A good way to understand these instructions is by seeing the machine operate. Let’s step the machine through the behavior defined by the table and see what happens (The machine is represented by the `<0>’ hovering above the tape, where 0 is the state the machine is in according to our table):

<0>
| 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<0>
| 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

In the above image, our machine is in STATE 0 and therefore keeps moving to the right whenever it encounters a marked cell (as defined in the table of behavior).

<0>
| 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<1>
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

When the machine (still in STATE 0) encounters a blank cell, it writes to the cell, switches to STATE 1, and moves right.

<1>
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

In STATE 1, the machine keeps scanning right, maintaining its current state. It continues right for as long as it reads dotted cells.

<1>
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<1>
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

Upon encountering an unmarked cell (while still in STATE 1), its
final action is to shift one cell to the left, erase, and stop.

<1>
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

We are now left with 7, the answer. Note that at no time did the machine understand the nature of what we call “addition”. It simply followed the instructions formalized in the table of behavior. It has no notion of its environment beyond the cell in front of it (It has no “memory”). It can only perform actions: read, write, erase, and move.

II

We’ve seen how to add two numbers using a simple Turing machine. Now let’s write a table of behavior for subtraction.

At this point, I challenge you to step away from the computer and do this yourself. You will learn more by attempting this than you will by reading about it here. Please do not come back until you have given it a try.


Welcome back. I assume that you’ve written a table of behavior for the subtraction operation. There are a number of tables that will work; here is one:

SYMBOL/STATE 1 0
0 RIGHT/STATE RIGHT/STATE
0 1
1 RIGHT/STATE RIGHT/STATE
2 1
2 LEFT/STATE 3 LEFT/STATE 5
3 ERASE/LEFT/STATE
4
4 ERASE/RIGHT/STATE LEFT/STATE 4
1
5 ERASE/LEFT/STATE
6
6 ERASE/STOP LEFT/STATE 6

Let’s trace the execution of the machine one step at a time as it subtracts 3 from 4.

In STATE 0, the machine moves to the right as it encounters filled cells. When it encounters a blank cell in STATE 0, the machine moves right and changes to STATE 1.

<0>
| 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<0>
| 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<1>
| 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

In STATE 1, the machine responds to a filled cell by moving right, and changing to STATE 2. In STATE 2, it shifts left and changes to STATE 3.

<2>
| 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<3>
| 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

In STATE 3, if it encounters a filled cell, the machine will erase,
move left, and change to STATE 4. In STATE 4, if a blank cell is
read, the machine moves left and remains in STATE 4.

<3>
| 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<4>
| 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

In STATE 4, when it encounters a filled cell, the machine erases, moves to the right, and changes to STATE 1. It then repeats (or recurs, if you will) through the steps shown above. We can see this in the next several illustrations.

<4>
| 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<4>
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<1>
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

All is as it was before. The machine is once again in STATE 1, poised above a filled cell. As before, it will shift right and enter STATE 2.

<1>
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<2>
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<3>
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<3>
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<4>
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<4>
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<4>
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<1>
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<1>
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

This time, however, the machine encounters a blank cell while in STATE 2. It shifts left and enters STATE 5.

<2>
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<5>
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

In STATE 5, the machine will erase the filled cell, shift left, and enter STATE 6. STATE 6 specifies that the machine will continue to shift left and remain in STATE 6 as long as it encounters blank cells.

<5>
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<6>
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

When the machine in STATE 6 encounters a filled cell, it will erase that cell and then stop. The subtraction is complete and we are left with the answer: 1.

<6>
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<6>
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

III

Here is the process shown in full without any verbal explication. The movements of the machine follow a predictable pattern. Note how the behavior of the machine during the transition between STATE 2 and STATE 5 as it nears the end of the computation resembles the base case of a recursive function 2. It’s quite beautiful.

<0>
| 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<0>
| 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<1>
| 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<2>
| 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<3>
| 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<3>
| 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<4>
| 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<4>
| 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<4>
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<1>
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<1>
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<2>
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<3>
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<3>
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<4>
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<4>
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<4>
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<1>
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<1>
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<2>
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<5>
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<5>
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<6>
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<6>
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

<6>
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

For a nice introduction to Turing Machines (among other things), I recommend Paul Hoffman’s book Archimedes’ Revenge.

(Image courtesy Melisande under Creative Commons license.)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s