[Back | Forward]

Turing Machines

Introduced by Alan Turing in 1936, Turing machines are one of the key abstractions used in modern computability theory, the study of what computers can and cannot do. A Turing machine is a particularly simple kind of computer, one whose operations are limited to reading and writing symbols on a tape, or moving along the tape to the left or right. The tape is marked off into squares, each of which can be filled with at most one symbol. At any given point in its operation, the Turing machine can only read or write on one of these squares, the square located directly below its "read/write" head.

In Turing's World the tape is represented by a narrow window that sits at the bottom of the screen. Here is what the tape looks like with a series of A's and B's written on it, and with the read/write head located on the leftmost of these symbols.

A Turing machine has a finite number of states and is in exactly one of these states at any given time. Associated with these states are instructions telling the machine what action to perform if it is currently scanning a particular symbol, and what state to go into after performing this action. The states of a Turing machine are generally represented by a flow or state diagram, using circles for the states and labelled arcs for the instructions associated with those states.

Here, for example, is a state diagram of a Turing machine with two states. When it is in state 0 looking at an A, this machine will move right one square and return to state 0. When it is in state 0 scanning a B, it will change this symbol to an A and go into state 1.

This machine will march right as long as it sees A's. When it encounters its first B, it will change this symbol to an A. It will then halt, since in state 1 it has no instructions telling it what to do when it sees an A (or any other symbol, for that matter).

In Turing's World, a collection of graphical tools lets you design Turing machines by directly drawing their state diagrams. Here is a simple machine designed using the tools shown on the left.

This machine will run down a string of A's and B's, stopping at the first A it sees after a B. For example, if run on the sample tape below, it would stop when it got to the fourth symbol from the left.

When you run a Turing machine in Turing's World, the operation of the machine is displayed graphically, both on the tape and in the state diagram window. On the tape, the read/write head moves, making the changes required by the machine you've designed. In the state diagram, the nodes and arcs highlight to show the changing state of the computation.

Despite their simplicity, Turing machines can be designed to compute remarkably complex functions. In fact, they are generally thought to be as powerful (in theory) as any possible computer. Finding out what they can do is half the fun of studying computability. Finding out what they can't do is the other half. [More]

Show me more.

Return to Logic Software from CSLI.