What is a TURING MACHINE?

In 1936 Alan Turing, a British Mathematician, came up with an idea for an imaginary machine that could carry out all kinds of computations on numbers and symbols. He believed that if you could write down a set of rules describing your computation his machine could faithfully carry it out. Turing's Machine is the cornerstone of the modern theory of computation and computability even though it was invented nine years before the creation of the first electronic digital computer. The Turing Machine consists of The Input/Output Tape is like the roll of paper you find on some printing calculators, only this roll of paper is infinitely long and is stretched like a scroll between two rollers so it can be wound forwards and backwards. The tape is divided into cells. The cells contain the input and output symbols and change frequently as a program is running.

The Turing Machine itself is pictured in this applet as some kind of mechanical 'black box' that sits above the tape and reads in symbols one at a time from its Read/Write head. The machine is always in a particular internal State indicated by a number on the box.

The Rule List is what determines the Machine's move at any particular point.

How it works

The Turing Machine reads a symbol from the Input/Output Tape and consults its Rule List. It then performs two actions.
  1. It modifies its internal State
  2. It writes a symbol on the tape
    Or
    Moves its R/W head left or right.
For example

Suppose the machine is in State 10 and the Read/Write head is positioned on the letter 'A'. The Turing Machine would consult its Rule List and possibly find the following rule:
10 A 12 >
This rule says: If you are in State 10 and reading an 'A' change to State 12 and advance the tape head to the right.

In this Turing Machine demo you can For a break, take a minute to 'talk' with Turing or check out a few of these sites for more information on the man and his machine. Enjoy!

More about Turing and his Machine

Run the Turing Machine applet
Back to the main Turing Machine page


ng@cs.brown.edu

Last modified: Wed Aug 28 19:52:42 EDT 1996