Turing Machines

Question

What is a Turing Machine? -Alan Turing

Answer

A Turing Machine is a theoretical idea, not a real machine. It helps to solve a difficult problem that have vexed philosophers since Hume. From Plato onward, it was assumed that people are able to represent knowledge in their mind somehow. Plato, for example, suggested that memory was like a wax tablet, and that experience made imprints on the tablet that could be read later. Hume realized that if there was something like a wax tablet, that someone (or something) would have to look at the tablet in order to retrieve the memory. This person in the head was called the homunculus.

The homunculus problem remained in Cognitive Science until the development of a theory of computation. The idea of computation is that some process is carried out on information represented in some kind of data structure. The data structure is like the wax tablet, and the process (sometimes called an algorithm) is the thing that looks at the wax tablet.

A Turing Machine is a demonstration that computations can be done without a homunculus. The machine has an infinitely long tape divided up into cells. Each cell can have some entry written in it, say a letter between A and Z. In addition, there is a set of "states" that the machine can be in that we can number. At any given moment, the machine knows what number state it is in, and can read the input in the cell it is on. Finally, the machine has a table that tells it that if it is in a particular state, and there is a particular entry on the tape what it should do. The actions that the machine can take are to replace the entry in the cell with something else (that is, to put another letter in the cell), to change to another state, and to move the tape one step to the right or to the left. At least one of the states in the table has to be the halting state, which is the state that stops the machine.

It turns out that with this simple machine, it is possible to set up a table and a tape in a way that any function a computer can perform can be done. The details of setting up a particular machine are complex, and we'll skip them here. If you're interested in the details, check out the book Turing's World by Barwise and Etchemendy.

One last point is important here. It turns out that it is possible to create what is called a Universal Turing Machine, which is a machine that can be configured to simulate any Turing machine. Modern digital computers are based on this concept, which is what allows them to compute any function.

Hope this helps.


Return to the PSY 355 Question Corner.
This page last modified on Monday, September 4, 2000.
You are visitor 969 to this page.