Editing Turing machine (section)

==Description==
{{for|examples of Turing machines|Turing machine examples}}

The Turing machine mathematically models a machine that mechanically operates on a tape.  On this tape are symbols, which the machine can read and write, one at a time, using a tape head. Operation is fully determined by a finite set of elementary instructions such as "in state 42, if the symbol seen is 0, write a 1; if the symbol seen is 1, change into state 17; in state 17, if the symbol seen is 0, write a 1 and change to state 6;" etc. In the original article ("[[On Computable Numbers, with an Application to the Entscheidungsproblem]]", see also [[#The Entscheidungsproblem (the "decision problem"): Hilbert's tenth question of 1900|references below]]), Turing imagines not a mechanism, but a person whom he calls the "computer", who executes these deterministic mechanical rules slavishly (or as Turing puts it, "in a desultory manner").

[[File:Turing machine 2a.svg|thumb|right|300px|The head is always over a particular square of the tape; only a finite stretch of squares is shown. The state of the machine (q<sub>4</sub>) is shown over the square to be processed. (Drawing after Kleene (1952) p. 375.)]]

[[File:Turing machine 2b.svg|thumb|right|300px|Here, the internal state (q<sub>1</sub>) is shown inside the head, and the illustration describes the tape as being infinite and pre-filled with "0", the symbol serving as blank. The system's full state (its "complete configuration") consists of the internal state, any non-blank symbols on the tape (in this illustration "11B"), and the position of the head relative to those symbols including blanks, i.e. "011B". (Drawing after Minsky (1967) p. 121.)]]

More explicitly, a Turing machine consists of:
* A ''tape'' divided into cells, one next to the other. Each cell contains a symbol from some finite alphabet. The alphabet contains a special blank symbol (here written as '0') and one or more other symbols. The tape is assumed to be arbitrarily extendable to the left and to the right, so that the Turing machine is always supplied with as much tape as it needs for its computation. Cells that have not been written before are assumed to be filled with the blank symbol. In some models the tape has a left end marked with a special symbol; the tape extends or is indefinitely extensible to the right.
* A ''head'' that can read and write symbols on the tape and move the tape left and right one (and only one) cell at a time. In some models the head moves and the tape is stationary.
* A ''state register'' that stores the state of the Turing machine, one of finitely many. Among these is the special ''start state'' with which the state register is initialised. These states, writes Turing, replace the "state of mind" a person performing computations would ordinarily be in.
* A finite ''table''<ref>Occasionally called an ''action table'' or ''[[transition system|transition function]]''.</ref> of instructions<ref>Usually quintuples [5-tuples]: q<sub>i</sub>a<sub>j</sub>→q<sub>i1</sub>a<sub>j1</sub>d<sub>k</sub>, but sometimes quadruples [4-tuples].</ref> that, given the ''state''(q<sub>i</sub>) the machine is currently in ''and'' the ''symbol''(a<sub>j</sub>) it is reading on the tape (the symbol currently under the head), tells the machine to do the following ''in sequence'' (for the 5-[[tuple]] models):
# Either erase or write a symbol (replacing a<sub>j</sub> with a<sub>j1</sub>).
# Move the head (which is described by d<sub>k</sub> and can have values: 'L' for one step left ''or'' 'R' for one step right ''or'' 'N' for staying in the same place).
# Assume the same or a ''new state'' as prescribed (go to state q<sub>i1</sub>).
In the 4-tuple models, erasing or writing a symbol (a<sub>j1</sub>) and moving the head left or right (d<sub>k</sub>) are specified as separate instructions. The table tells the machine to (ia) erase or write a symbol ''or'' (ib) move the head left or right, ''and then'' (ii) assume the same or a new state as prescribed, but not both actions (ia) and (ib) in the same instruction. In some models, if there is no entry in the table for the current combination of symbol and state, then the machine will halt; other models require all entries to be filled.

Every part of the machine (i.e. its state, symbol-collections, and used tape at any given time) and its actions (such as printing, erasing and tape motion) is ''finite'', ''discrete'' and ''distinguishable''; it is the unlimited amount of tape and runtime that gives it an unbounded amount of [[Computer storage|storage space]].