336 !;! Theory ofComputer Science
(vi) Then the head scans the second 1 of the input string and moves right,
and M enters qo (q s 1Rqo).
Operations (i)-(vi) are repeated until all the 1's of the input part
(i.e. in 1 ii1 ) are exhausted and 11 ... 1 (al times) appear to the left
of y. Now the present state is qo, and the current symbol is Xj.
(vii) M in state qo scans Xl, moves right. and enters CJ6' It continues to move
to the right until it encounters y (CJox l RCJ6, q6bRCJ6, CJ6 1RCJ6, CJfrYIRCJ6)'
(viii) On encountering y. the head moves to the left and M enters CJ7, after
which the head moves to the left until it encounters b appearing to the
left of 1"1 of the output part. This b is changed to 1, and M enters
CJs (CJ6yLCJ7. q l lLq7, q7 b jCJS)'
(ix) Once M is in qs, the head continues to move to the left and on scanning
Xl. M enters CJ9' As there is no quadruple starting with q9, M halts
(qsbLqs· CJ s ILqs, qsxIXICJ9)'
The machine halts, and the terminal ill is 1Ulq9Xjl"I+1y. For example, let
us compute S(I). In this case the initial ill is CJolx] by. As a result of the
computation, we have the following moves:
CJOlxlby 1- CJjbxjby r- bCJ]xjby
f- bXICJ/J)'I- bx1bqlY r- bx jbCJ:1
r- bx lblCJ2 b r- bx lblq3Y r- bx l bCJ3 1 y
r- bCJ,x l b1y r- CJ4 bx l b1 y r- qslx 1b1y
r- 1CJ6- y j bh r- 1x jb1CJ6Y r- l.y lbq7 1y
r- LrjCJ7b1y r- lxjCJsllv r- 1Qsxj lly
r- lCJ9x j 11y
Thus. M halts and SO) = 2 (given by 11 to the left of y).
11.4.6 CONSTRUCTION OF THE TURING MACHINE FOR
COMPUTING THE PROJECTION Ur
Recall Ut'(al' .... a/l1) = ai' The initial tape expression can be taken as
We define a Turing machine by taking Q = {qo, ..., qs}
r = {b. L Xl> .... XII!' y}. P consists of
qozRqo
qoxiLqj.
CJ:;:RCJ:
CJ::vlCJ,·
for all ;: E r - {x;}
qlbbqg' qlbq:
for all ;: E r - {y}
q3 1R q3' q3 b YCJ4