Computability - Models of Computation: Exploring the Power of Computing - page 218

5.3 Configuration Graphs
We now introduce configuration graphs, graphs that capture the state of Turing machines
with potentially unlimited storage capacity. We begin by describing configuration graphs for
one-tape Turing machines.

DEFINITION 5.3.1 The configuration of a standard Turing machine M at any point in time
is [ x 1 x 2 ... p x j ...x n ] ,where p is the state of the control unit, the tape head is over the j th tape
cell, and x =( x 1 , x 2 , ... , x n ) is the string that contains all the non-blank symbols on the tape as
well as the symbol under the head. Here the state p isshowninboldfacetotheleftofthesymbol x j to
indicate that the tape head is over the j th cell. x n and some of the symbols to its left may be blanks.

To illustrate such configurations, consider a TM M that is in state p reading the third
symbol on its tape, which contains xyz . This information is captured by the configuration
[ xy p z ] . f M changes to state q and moves its head right, then its new configuration is
[ xyz q β ] . In this case we add a blank β to the right of the string xyz to insure that the head
resides over the string.
Because multi-tape TMs are important in classifying problems by their use of temporary
work space, a definition for the configuration of a multi-tape TM is desirable. We now intro-
duce a notation for this purpose that is somewhat more cumbersome than used for the standard
TM. This notation uses an explicit binary number for the position of each tape head.

DEFINITION 5.3.2 The configuration of a k -tape Turing machine M is ( p , h 1 , h 2 , ... , h k ,
x 1 , x 2 , ... , x k ) ,where h r

is the position of the head in binary on the r th tape, p is the state of
the control unit, and x r is the string on the r th tape that includes all the non-blank symbols as well
as the symbol under the head.

We now define configuration graphs for deterministic TMs and NDTMs. Because we will
apply configuration graphs to machines that halt on all inputs, we view them as acyclic.

DEFINITION 5.3.3 A configuration graph G ( M ND , w ) associated with the NDTM M ND is a
directed graph whose vertices are configurations of M ND .(SeeFig. 5.9 .) There is a directed edge
between two vertices if for some choice input vector c M ND can move from the first configuration to

Figure 5.9 The configuration graph G ( M ND ,

w ) of a nondeterministic Turing machine M ND

has one vertex for each configuration of M ND . The graph is acyclic. Heavy edges
identify the nondeterministic choices associated with each configuration.

w

on input