Turing machine

Turing machine, a mathematical model of a device that computes via a series of discrete steps and is not limited in use by a fixed maximum amount of data storage. Introduced by the British mathematician Alan Turing in 1936, a Turing machine is a particularly simple computer, one whose operations are limited to reading and writing symbols on tape, or moving along the tape to the left or to the right one symbol at a time. Its behavior at a given moment is determined by the symbol in the square currently being read and by the current state of the machine. The theoretical prototype of the electronic digital computer, Turing machines are one of the key abstractions used in modern computability theory, the study of what computers can and cannot do. Appropriate Turing machines have found application in the study of artificial intelligence, the structure of languages, and pattern recognition.

The Columbia Electronic Encyclopedia, 6th ed. Copyright © 2024, Columbia University Press. All rights reserved.

See more Encyclopedia articles on: Computers and Computing