turing machines (TM) are named after Alan Turing, who invented them in 1936. turing machines can compute any function normally considered computable; in fact, it is quite reasonable to define computable to mean computable by a TM. we describe here a deterministic, one-tape Turing machine. this is the standard off-the-shelf model. there are many variations, apparently more powerful or less powerful but in reality not.
a TM has a finite set of states , a semi-infinite tape that is delimited on the left end by an endmarker and is infinite to the right, and a head that can move left and right over the tape, reading and writing symbols.
the input string is of finite length and is initially written on the tape in contiguous tape cells snug up against the left endmarker. the infinitely many cells to the right of the input all contain a special blank symbol .
the machine starts in its start state with its head scanning the left endmarker. in each step it reads the symbol on the tape under its head. depending on that symbol and the current state, it writes a new symbol on that tape cell, moves its head either left or right one cell, and enters a new state. the action it takes in each situation is determined by a transition function . it accepts its input by entering a special accept state and rejects by entering a special reject state . on some inputs it may run infinitely without ever accepting or rejecting, in which case it is said to loop on that input.
a deterministic one-tape turing machine is a 9-tuple where
- is a finite set (the states);
- is a finite set (the input alphabet);
- is a finite set (the tape alphabet) containing as a subset;
- , the blank symbol;
- , the left endmarker;
- , the transition function;
- , the start state;
- , the accept state; and
- , the reject state; .
intuitively, means, "when in state scanning symbol , write on that tape cell, move the head in direction , and enter state ." the symbols and stand for left and right, respectively.
we restrict TMs so that the left endmarker is never overwritten with another symbol and the machine never moves off the tape to the left of the endmarker; that is, we require that for all there exists such that
we also require that once the machine enters its accept state, it never leaves it, and similarly for its reject state; that is, for all there exist and such that
we sometimes refer to the state set and transition function collectively as the finite control.
a Turing machine is a kind of idealized typewriter with an infinite tape and a reading head moving back and forth one cell at a time according to a finite state program. in 1936 Turing demonstrated convincingly that this mathematical model captured the informal notion of effectively calculable. turing's model and analysis have been accepted ever since as the most convincing model.
a Turing machine includes a two-way infinite tape divided into cells, a reading head which scans one cell of the tape at a time, and a finite set of internal states . each cell is either blank (B) or has written on it the symbol 1. in a single step the machine may simultaneously: (1) change from one state to another; (2) change the scanned symbol to another symbol ; and (3) move the reading head one cell to the right ( ) or left ( ). the operation of is controlled by a partial map (which may be undefined for some arguments).
a figure illustrating the turing machine
the interpretation is that if then the machine in state , scanning symbol , changes to state , replaces by , and moves to scan one square to the right if (or left if ). the map viewed as a finite set of quintuples is called a Turing program. the input integer is represented by a string of consecutive 1’s (with all other cells blank). the Turing machine is pictured in (in robert i. soare, 2016 chapter 1 figure 1.1).
we begin with in the starting state scanning the leftmost cell containing a 1, called the starting cell. if the machine ever reaches the halting state , after say steps, then we say halts and the output is the total number of 1's on the tape. (note that bounds the maximum distance from the starting cell to any cell which is either scanned or contains an input symbol. hence the determination of is effective.)
we may assume that never makes any further moves after reaching state , i.e., that the domain of contains no element of the form . we say that computes the partial function provided that if and only if with input eventually halts and yields output . for example, the following machine computes the function .
the instantaneous condition of during each step in a turing calculation is completely determined by: (1) the current state of the machine; (2) the symbol being scanned; (3) the symbols on the tape to the right of symbol up to the last 1, i.e., ; and (4) the symbols to the left of up to the first 1, i.e., . this is the (instantaneous) configuration of the machine at that step and is written
for example, the machine of eq-turing-machine-1 in calculating on input passes through the configurations, , and , and it yields output . (recall that the input is coded by consecutive 1's while the output is coded by the total number of 1's on the tape. also notice that the tape contains only finitely many non-blank symbols at the beginning of any calculation and that this condition persists at all later stages, whether the machine halts or not, so that the integers and in eq-turing-machine-2 exist.)
if the machine enters a state and reads a symbol from which gives no moves, then the machine stalls, i.e., makes no further moves, and gives no output. we do not refer to this as halting even though the machine stalls and stops forever. we use the term halting only if enters the halting state .
a Turing computation according to Turing program with input is a sequence of configurations, such that represents the machine in the starting state reading the leftmost symbol of the input , represents the machine in the halting state , and the transition , for all , is given by the Turing program .
thus, from now on a computation will always refer to a halting, i.e., convergent, calculation. a partial function of variables is associated with each Turing machine by representing the input by the following initial configuration of where consists of consecutive 1's.
given inputs , we represent these as an input to a Turing machine by writing each as a block of 1's and separating each block by a .
(taken from robert i. soare, 2016 chapter 1 defining computability)