292 ~ Theory of Computer Science
of COPY. The TM Ail performs the subroutine COPY. The following moves
take place for M 1 : q101711- 2q=:017-11 P- 20n-11q3b f- 20n-1q31O P- 2q j O"-llO.
After exhausting O·s. q1 encounters 1. M 1 moves to state q4' All 2's are
converted back to 0' sand M 1 halts in qs. The TM M picks up the computation
by starting from qs. The qo and q6 are the states of M. Additional states are
created to check whether each °in 0
11I gives rise to 0
11I at the end of the
rightmost 1 in the input string. Once this is over, M erases 10"1 and finds 0"111
in the input tape.
M can be defined by
M = ({qo. qj, .... qd· {O. I}, {O, 1,2, b}, 8, qo, b. {qd)
where 8 is defined by Table 9.8.
TABLE 9.8 Transition Table for Example 9.10
°
2
qo
q6bR
q6
q60R
q, 1R
q5
q70 L
q7
q s 1L
qs
qgOL
qg
qgOL
q,0
q" bR
q,1
q" bR
q,2 bR
b
q1QbR
qobR
Thus M performs multiplication of two numbers in unary representation.
9.7 VARIANTS OF TURING MACHINES
The Turing machine we have introduced has a single tape. 8(q, a) is either a
single triple (p, y, D), where D = R or L, or is not defined. We introduce two
new models of TM:
(i) a TM with more than one tape
(ii) a TM where 8(q. a) = {(PJo YJ, D j ), (P=:, Y=:. D 2 ), •••• (p,., Yn Dr)}' The
first model is called a multitape TM and the second a nondeterministic
TM.
9.7.1 MULTITAPE TURING MACHINES
A multitape TM has a finite set Q of states. an initial state qo. a subset F of Q
called the set of final states. a set P of tape symbols. a new symbol b. not in
P called the blank symbol. (We assume that :2: ~ rand b EO :2:.)