Let us now look at the procedure to compute functions f n n
n k
( , ,
)
1
2 KK
where n n
n k
1
2
, ,
,
KK
are non-negative integers.
(a) Represent the integers n n
n k
1
2
, ,
,
KK
in unary i.e., n 1 is written
as 0
1
n
etc. The input ( , , , )
n n
n k
1
2 K
is represented by
0 10
10
1
2
n
n
n k
KK
where the 1’s are used to separate the unary
representation of n n
n k
1
2
, ,
,
KK
.
(b) After several moves, if the Turing Machine halts (either in a
final state or in any other state) and has 0
m in the input tape, then
F (n n
n k
1
2
, ,
,
KK
) = m.
Ì Exam ple 4.2.1: Design a Turing machine to add two given integers.
Solu tion
Assume that m and n are positive integers. Let us represent the input as 0
m B0
n .
If the separating B is removed and 0’s come together we have the required
output, m + n is unary.
(i) The separating B is replaced by a 0.
(ii) The rightmost 0 is erased i.e., replaced by B.
Let us define M
q q q q q
B
q q
= ({ , , , , }, { }, { , }, , , { })
0
1
2
3
4
0
4
0 0
δ
. δ is
defined by Table shown below.
Tape Sym bol
State
0
B
q 0
( , , )
q
R
0 0
( , , )
q
R
1 0
q 1
( , , )
q
R
1 0
( , , )
q B L
2
q 2
( , , )
q B L
3
—
q 3
( , , )
q
L
3 0
( , , )
q B R
4
M starts from ID q
B
m
n
0 0 0 , moves right until seeking the blank B. M
changes state to q 1 . On reaching the right end, it reverts, replaces the rightmost
0 by B. It moves left until it reaches the beginning of the input string. It halts at
the final state q 4 .
Ì Exam ple 4.2.2: Design a Turing Machine that copies strings of 1’s.
Solu tion
Follow the following steps:
Turing Machines
193