turing machine

<2023-11-16 Thu 15:22:35> mahmood
cs
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.
[cite:;taken from @kozen_automata_1997 lecture 28 turing machines and effective computability]
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.
[cite:;taken from @computability_soare_2016 introduction]
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).
[cite:;taken from @computability_soare_2016 definition 1.4.1]
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 [cite:;in @computability_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 turing_machine.html 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 turing_machine.html 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 .
[cite:;taken from @computability_soare_2016 definition 1.4.2]
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 .
[cite:;taken from @computability_soare_2016 definition 1.4.3]
[cite:;taken from @computability_soare_2016 chapter 1 defining computability]
a tape is an infinite one-directional line of cells, each of which can hold a symbol from a finite set called the alphabet of the machine. each tape is equipped with a tape head that can potentially read or write symbols to the tape one cell at a time. the machine's computation is divided into discrete time steps, and the head can move left or right one cell in each step.
the first tape of the machine is designated as the input tape. the machine's head can only read symbols from that tape, not write them--a so-called read-only head. the read-write tapes are called work tapes, and the last one of them is designated as the output tape of the machine, on which it writes its final answer before halting its computation.
[cite:;taken from @computability_arora_2009 chapter 1.2 the turing machine]
the only difference between a nondeterministic turing machine (NDTM) and a standard TM is that an NDTM has two transition functions and , and a special state denoted by . when an NDTM computes a function, we envision that at each computational step makes an arbitrary choice as to which of its two transition functions to apply. for every input , we say that if there exists some sequence of these choices (which we call the nondeterministic choices of ) that would make reach on input . otherwise--if every sequence of choices makes halt without reaching --then we say that . we say that runs in time if for every input and every sequence of nondeterministic choices, reaches either the halting state or within steps.
[cite:;taken from @computability_arora_2009 chapter 2.1.2 nondeterministic turing machines]
let be a TM. a configuration of a TM consists of the contents of all nonblank entries of 's tapes, along with its state and head position, at a particular point in its execution. for every space TM and input , the configuration graph of on input , denoted , is a directed graph whose nodes correspond to all possible configurations of where the input contains the value and the work tapes have at most nonblank cells. the graph has a directed edge from a configuration to a configuration if can be reached from in one step according to 's transition function. if is deterministic, then the graph has out-degree one, and if is nondeterministic, then the graph has out-degree at most two. by modifying to erase all its work tapes before halting, we can assume that there is only a single configuration on which halts and outputs 1. this means that accepts the input iff there exists a directed path in from to .
[cite:;taken from @computability_arora_2009 chapter 4.1 definition of space-bounded computation]
let be the configuration graph of a space- machine on some input of length . then,
  • every vertex in can be described using bits for some constant (depending on 's alphabet size and number of tapes) and in particular, has at most nodes.
  • there is an -size cnf formula such that for every two strings , if and only if and encode two neighboring configurations in
[cite:;taken from @computability_arora_2009 claim 4.4]