DHARM
N-COM\CMS12-1.PM5346 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCENumber 0 is represented by 0
Number 1 is represented by 00
Number 2 is represented by 000
Number 3 is represented by 0000
....... ...
....... ...
....... ...
Number k is represented by (k + 1) 0’s
Thus number u and v are represented by (u + 1) 0’s and (v + 1) 0’s respectively. These
streams of 0’s are loaded on the tape of the Turing machine. To distinguish numbers u and v
we introduced a separator 1 between them. This number 1 is called the breaker. Fig. 12.18
shows the tape cells entries before the start of the machine.
( + 1)0’su ( + 1)0’svq 0 Breaker0001 0 BBBFig. 12.18
Fig. 12.19 shows the situation of the Turing machine computation for the function f
which is outputted w i.e., a stream of (w + 1) 0’s in finite steps, where X’s are the tape symbols
that comes after the replacement of input symbol 0’s.
( + 1)0’swpX ...... X 0 0 0 BBBFig 12.19
Consider an example to construct a Turing machine for the function f which evaluate
the addition of two numbers x 1 and x 2 , i.e.,
f(x 1 , x 2 ) = x 1 + x 2
Since, f is the natural function so we can construct an equivalent Turing machine for
the addition of two numbers x 1 , x 2. As per the requirement we can assume that numbers x 1 and
x 2 are represented by (x 1 + 1) 0’s and (x 2 + 1) 0’s and these streams of 0’s are to be placed on the
tape cells of the machine with the breaker 1. Fig 12.20 pictured the above situation.