Chapter 9: Turing Machines and Linear Bounded Automata ~ 291
First a TM program for the subroutine is written. This will have an initial
state and a 'return' state. After reaching the return state. there is a temporary
halt. For using a subroutine, new states are introduced. When there is a need
for calling the subroutine, moves are effected to enter the initial state for the
subroutine (when the return state of the subroutine is reached) and to return to
the main program of TM.
We use this concept to design a TM for perfonning multiplication of two
positive integers.
EXAMPLE 9.10
Design a TM which can multiply two positive integers.
Solution
The input (m, 11). m. 11 being given, the positive integers are represented by
0
111 10". M starts with 0
111 10" in its tape. At the end of the computation,
O"ill(mn in unary representation) sUlTounded by b's is obtained as the ouput
The major steps in the construction are as follows:
1. OIl! 10
11 1 is placed on the tape (the output will be written after the
rightmost 1).
2. The leftmost °is erased.
3. A block of 11 O's is copied onto the right end.
4. Steps 2 and 3 are repeated 111 times and 10
1
"10""
1 is obtained on the
tape.
5. The prefix 101/11 of 101/110
/11
" is erased. leaving the product mn as the
output.
For every 0 in Olil. 0" is added onto the right end. This requires repetition
of step 3. We define a subroutine called COPY for step 3.
For the subroutine COPY. the initial state is qj and the final state is qs. (5
is given by the transition table (see Table 9.7).
TABLE 9.7 Transition Table for Subroutine COpy
State
Tape symbol
°
2
b
q22R
q4 1L
q20 R
q2 1R
q30 L
q30 L
q3 1L
q1 2R
Q s 1R
Q40L
The Turing machine M has the initial state qo. The initial ill for M is
Cf o O
Ill 10"1. On seeing 0. the following moves take place (q6 is a state of M).
CfrP"10
1I 1 t- bq601ll-1101I1 ~ bO
Ill
-
1
q6 1O"1 t- bO
Ill
-
1 1q j O"1. qj is the initial state