Turing machine

A Turing machine has finitely many control states and a finite tape alphabet. Its tape consists of cells that a head can read and rewrite. The current state and scanned symbol determine the symbol to write, the head's movement and the next state. Common definitions allow left and right movement; some also permit staying in place.

The input occupies a finite region and the remaining cells are blank. Available tape has no predetermined capacity, although a computation lasting finitely many steps visits only finitely many cells. This separates computability in principle from a shortage of storage; it does not require building an actual infinite tape.

References: [1] [3]

Writing makes it possible to retain intermediate information and revisit it. For a small example, represent a nonnegative integer by a block of ones, with the empty string representing zero. Start the head at the input's left end. To add one, move right across every one, write a one in the first blank cell, and halt. Thus 111 becomes 1111, while an empty input becomes 1.

The number of rules for this procedure does not grow with the input, but the number of executed steps does. More elaborate procedures can mark processed positions with extra symbols and scan back and forth. Finite control combined with writable workspace therefore differs from an automaton that retains its entire memory in a fixed state set.

References: [1]

A machine's finite states and rules can be encoded as a finite string. A universal Turing machine takes another machine's description together with its input, interprets the description and simulates successive actions. Universality means performing the encoded computation, not knowing its outcome in advance.

If the simulated computation continues forever, the simulation can continue forever too. The halting problem rules out an always-terminating, uniformly correct procedure for predicting termination for every machine and input. Running a program and completely predicting arbitrary programs are different capabilities.

References: [4] [3]

Multiple tapes can be simulated on one tape, and nondeterministic Turing machines can be simulated deterministically. These equivalences concern which languages or functions are computable; they do not assert identical running times. Simulation overhead remains relevant to computational complexity even when computability is unchanged.

Turing introduced abstract machines in his 1936–1937 work on computable numbers and the decision problem. Modern standard definitions need not match every detail of his original presentation. Physical computers have finite memory, particular instruction sets and engineering constraints. The tape model instead offers a deliberately simple framework for proofs. It is neither a literal blueprint for a processor nor a claim that real machines possess unlimited resources.

References: [2] [3]