What is a Turing machine?

A Turing machine is a mathematical model of computation that describes an abstract machine manipulating symbols on a strip of tape according to a table of rules. Despite its simplicity, it can implement any computer algorithm. It is not a physical device but an idealised one, used to give a precise, formal meaning to what it is for a function to be computable. [1] [2]

The machine works on a memory tape divided into cells, each holding one symbol from a finite alphabet. A head sits over one cell at a time, and the machine is always in one state drawn from a finite set. The tape is treated as unbounded in length, because Turing's aim was to show that some tasks are impossible even with unlimited working memory and unlimited time. The input written on the tape at the start, however, must be a finite number of symbols. [1] [3]

The tape serves as input, output and working memory all at once. When a computation finishes, the machine halts, and the result can be read from the tape. [3]

At each step the head reads the symbol in its cell. Based on that symbol and the current state, a finite table of instructions says what to write, which way to move, and which state to enter next, or whether to halt. Each instruction has the form: if the state is n and the symbol under the head is x, write y, go into state m, and move left, move right or halt. This table is the machine's program. [1] [3]

Turing's own machines were deterministic, which he called automatic machines: the current state and scanned symbol completely fix the next action. He contrasted them with choice machines, whose next step depends on an external operator. Presentations differ in detail. The Stanford Encyclopedia notes that Turing himself used varying notations, and that some versions allow the head to stay in place. As with ordinary programs, a Turing machine can fall into an infinite loop and never halt. [4] [1]

Alan Turing introduced the idea in his 1936 paper on computable numbers and the Entscheidungsproblem. The name "Turing machine" came from Alonzo Church, who used it in a review of that paper. Today the model is considered one of the foundational models of computability and theoretical computer science. [2] [4]

Many other definitions of computation have been proposed, such as running a Java program on a computer with infinite memory, but all known definitions agree with the Turing machine on what is computable and what is not. The Turing machine is the simplest of them, which is why it is commonly taught first. Its features are finite internal state, unlimited external storage, a finite program, and the ability to express an interpreter for its own programs. A consequence is that the model captures what any digital computer can compute, and that some problems are out of reach for computers however fast or large. [5] [6] [2]