Turing machines were invented by Alan Turing, the father of computer science, in 1936. He wanted to define what an algorithm is in precise mathematical terms. His definition turned out to also be the most useful model of a computer to this date.
A Turing machine consists of a processor and an infinite tape with a "start" space on which symbols can be written or erased. The machine begins when it is fed a tape with zeros and ones already written on it (or it could be blank). The processor first reads the symbol in the "start" space. The processor remembers only one number, called its state. It moves back and forth along the tape, reading and writing symbols and changing its state. At each step in the calculation, the action of the processor depends on only two things: its current state number and the symbol currently being read. It stops processing only if its state changes to the "halt" state. The output can then be read from the tape. The number of possible states for the processor is finite. So, any Turing machine can be specified by the following finite table. The table has the processor's states listed horizontally at the top and the symbols 0, 1 and blank are written vertically on the side. Then for each state and symbol pair, the action (either move left, move right, halt, write 0, write 1, or erase the current symbol) is written in the appropriate space.
Turing also proved the existence of a Universal Turing machine. Such a machine can mimic any Turing machine. Since Turing machines can all be specified by a finite amount of information, the number of Turing machines is denumerable. Hence each can be assigned to a natural number so that no two Turing machines are assigned the same number. When you want a universal Turing machine to mimic a Turing Machine named Bob, say, then you find Bob's number and translate it into 1's and 0's. You feed this to the Universal Machine and then whatever input you put into the Universal Machine it will process just as Bob would. It is Church's thesis that a Universal Turing machine can do anything any modern computer can do.
Turing also proved that no Turing machine can determine whether any given Turing machine will halt on a given input. This fact is referred to as the undecidability of the halting problem. It is equivalent to the statement that there is no Turing machine that can determine whether any two given Turing machines always produce the same output when given the same input. This fact has profound applications to logic, group theory, tesselations, and many other areas of mathematics.
Turing also defined computable numbers. A Turing machine's input is just a string of 1's, 0's and blanks and so is its output. Therefore every Turing machine can be represented as a function f say, from a subset of natural numbers to the natural numbers. The domain of f is the subset on which the Turing machine halts. Since the rationals can be put into correspondence with the natural numbers by some function, g say, we can compose g with f to obtain a function from a subset of the natural numbers to the rationals. If the domain of f is the whole set of natural numbers and the sequence {f(n)} converges to a real number x then x is said to be computable. Turing proved that the set of computable numbers is a field and that Pi is computable. The set of computable numbers contains the set of constructible numbers (see Euclidean construction) since those are just numbers which are computed from a special type of algorithm involving ruler and compass.
Turing machines are used to estimate computing speed. For example, suppose that there is a function f from the natural numbers to the rationals that we wish to compute. We find or make a Turing machine that computes f. We then note how many cells the processor must visit in order to compute f(n) for each n. The number of cells is called the cost of computation (for this example). We then multiply by a suitable constant that depends on how fast our computer really is. For example, the constant might be 1/100 of a second. Now we have an idea of how fast our algorithm is, even before writing it into a computer. The study of computing speed is fundamental to abstract complexity theory, an important part of computer science.
For more on Turing machines and decidability see Computability: A Mathematical Sketchbook by Douglas Bridges (Springer Verlag, 1994).
This is the complete article, containing 767 words
(approx. 3 pages at 300 words per page).
