762
Modeling Arithmetic, Computation, and Languages
the configuration illustrated in Figure 9.16b. The symbol 1 being read on the tape
has been changed to a 0, the state of the unit has been changed from 2 to 1, and the
head has moved one cell to the right.
The term “Turing machine” is used both in the generic sense and also as
the collection of quintuples that describe the actions of any particular machine. This is the same double usage for both the name of the abstraction
and any instance of that abstraction that we mentioned for Boolean algebra in
Chapter 8.
Definition turinG MAChinE
Let S be a finite set of states and I a finite set of tape symbols (the tape alphabet)
including a special symbol b. A turing machine is a set of quintuples of the
form (s, i, i′, s′, d) where s, s′ [ S; i, i′ [ I; and d [ 5R, L6 and no two
quintuples begin with the same s and i symbols.
The restriction that no two quintuples begin with the same s and i symbols
ensures that the action of the Turing machine is deterministic and completely
specified by its present state and symbol read. If a Turing machine gets into a configuration for which its present state and symbol read are not the first two symbols
of any quintuple, the machine halts.
Just as in the case of ordinary finite-state machines, we specify a fixed starting state, denoted by 0, in which the machine begins any computation. We also
assume an initial configuration for the read–write head, namely, a position over
the farthest left nonblank symbol on the tape. (If the tape is initially all blank, the
read–write head can be positioned anywhere to start.)
example 40
A Turing machine is defined by the set of quintuples:
(0, 0, 1, 0, R)
(0, 1, 0, 0, R)
(0, b, 1, 1, L)
(1, 0, 0, 1, R)
(1, 1, 0, 1, R)
The action of this Turing machine when processing a particular initial tape is
shown by the sequence of configurations in Figure 9.17, which also shows the
quintuple that applies at each step. Again, which quintuple applies is determined by the present state and present symbol; as a result, the order in which
quintuples are applied has nothing to do with the order in which they are presented in the machine’s definition, quintuples can be used more than once, or
may not be used at all.
Modeling Arithmetic, Computation, and Languages
the configuration illustrated in Figure 9.16b. The symbol 1 being read on the tape
has been changed to a 0, the state of the unit has been changed from 2 to 1, and the
head has moved one cell to the right.
The term “Turing machine” is used both in the generic sense and also as
the collection of quintuples that describe the actions of any particular machine. This is the same double usage for both the name of the abstraction
and any instance of that abstraction that we mentioned for Boolean algebra in
Chapter 8.
Definition turinG MAChinE
Let S be a finite set of states and I a finite set of tape symbols (the tape alphabet)
including a special symbol b. A turing machine is a set of quintuples of the
form (s, i, i′, s′, d) where s, s′ [ S; i, i′ [ I; and d [ 5R, L6 and no two
quintuples begin with the same s and i symbols.
The restriction that no two quintuples begin with the same s and i symbols
ensures that the action of the Turing machine is deterministic and completely
specified by its present state and symbol read. If a Turing machine gets into a configuration for which its present state and symbol read are not the first two symbols
of any quintuple, the machine halts.
Just as in the case of ordinary finite-state machines, we specify a fixed starting state, denoted by 0, in which the machine begins any computation. We also
assume an initial configuration for the read–write head, namely, a position over
the farthest left nonblank symbol on the tape. (If the tape is initially all blank, the
read–write head can be positioned anywhere to start.)
example 40
A Turing machine is defined by the set of quintuples:
(0, 0, 1, 0, R)
(0, 1, 0, 0, R)
(0, b, 1, 1, L)
(1, 0, 0, 1, R)
(1, 1, 0, 1, R)
The action of this Turing machine when processing a particular initial tape is
shown by the sequence of configurations in Figure 9.17, which also shows the
quintuple that applies at each step. Again, which quintuple applies is determined by the present state and present symbol; as a result, the order in which
quintuples are applied has nothing to do with the order in which they are presented in the machine’s definition, quintuples can be used more than once, or
may not be used at all.