14 1 Computational Tasks and Models
Providing a concrete representation of the successive configuration function
requires providing a concrete representation of instantaneous configurations.
For example, we may represent each instantaneous configuration of a machine
with symbol set and state set Q as a triple (α, q, i), where α ∈
∗
, q ∈ Q and
i ∈{1, 2,...,|α|}.LetT : × Q → × Q ×{−1, 0, +1} be the transition
function of the machine. Then, the successive configuration function maps
(α, q, i)to(α
,q
,i + d) such that α
differs from α only in the i
th
location,
which is determined according to the first element in T (α
i
,q). The new state
(i.e., q
) and the movement (i.e., d) are determined by the other two elements
of T (α
i
,q). Specifically, except for some pathological cases, the successive
configuration function maps (α, q, i)to(α
,q
,i + d) if and only if T (α
i
,q) =
(α
i
,q
,d) and α
j
= α
j
for every j = i, where α
j
(resp., α
j
) denotes the j
th
symbol of α (resp., α
). The aforementioned pathological cases refer to cases
in which the machine resides in one of the “boundary locations” and needs to
move farther in that direction. One such case is the case that i = 1 and d =−1,
which causes the machine to halt (rather than move left of the left boundary of
the tape). The opposite case refers to i =|α| and d =+1, where the machine
moves to the right of the rightmost non-blank symbol, which is represented by
extending α
with a blank symbol “-” (i.e., |α
|=|α|+1 and α
|α|+1
= -).
Initial and Final Environments. The initial environment (or configuration)
of a Turing machine consists of the machine residing in the first (i.e., leftmost)
cell and being in its initial state. Typically, one also mandates that in the initial
configuration, a prefix of the tape’s cells holds bit values, which concatenated
together are considered the
input, and the rest of the tape’s cells hold a special
(“blank”) symbol (which in Figures 1.1 and 1.2 is denoted by “-”). Thus, the
initial configuration of a Turing machine has a finite (explicit) description. Once
the machine halts, the
output is defined as the contents of the cells that are to
the left of its location (at termination time).
4
Note, however, that the machine
need not halt at all (when invoked on some initial environment).
5
Thus, each
machine defines a (possibly partial) function mapping inputs to outputs, called
the
function computed by the machine. That is, the function computed by machine
M maps x to y if, when invoked on input x, machine M halts with output y,
and is undefined on x if machine M does halt on input x.
4
By an alternative convention, the machine must halt when residing in the leftmost cell, and the
output is defined as the maximal prefix of the tape contents that contains only bit values. In such
a case, the special non-Boolean output ⊥ is indicated by the machine’s state (and indeed in this
case the set of states, Q, contains several halting states).
5
A simple example is a machine that “loops forever” (i.e., it remains in the same state and the
same location regardless of what it reads). Recall, however, that we shall be mainly interested in
machines that do halt after a finite number of steps (when invoked on any initial environment).