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
- an Input/Output Tape,
- the Turing Machine itself,
- and a Rule List
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.
- It modifies its internal State
- 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
- Load sample programs and run them.
- Write your own rules and set up the Tape any way you want.
- Experiment with programs by editing the rules, tape, and internal State on the fly.
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