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)