Turing machine
A very simple imaginary machine that does nothing but read and write symbols on a tape. Alan Turing devised it in 1936 to define what it means for something to be computable.
The machine reads one square of a long tape, rewrites the symbol according to fixed rules, moves the tape one square, and repeats. Turing argued that anything a person can calculate by following a procedure can be done by such a machine, and at the same time proved that there are problems no machine can answer[1].
He also showed that if the rules themselves are written on the tape, a single machine, the universal machine, can imitate any other Turing machine. That is the guarantee that a new machine need not be built for each calculation. A computer's ability to do anything simply by changing its program rests on this result.
Related terms
- Stored-program computerA computer design in which the procedure to be followed, the program, is kept in the same memory as the data. Almost every computer today works this way.
- Boolean algebraMathematics that represents true and false as 1 and 0 and calculates with AND, OR and NOT much as with addition and multiplication. The foundation of digital circuit design.