Chapter 11: Computability ~ 337
qJ.zLqJ.
for all z E 1- {x;}
qJ.xiLqS,
qsILqs,
qsblq6'
q6 ILq7,
q7 Ibq2
q7zRqS
for all z E f- {I}
The operations of M are as follows:
(i) M starts from the initial ill and the head moves to the right until it
encounters Xi (qozRqo)·
(ii) On seeing Xi, the head moves to the left (qoXiLql)'
(iii) The head replaces 1 (the rightmost 1 in l
a ;) by b (q 1 lbq2)'
(iv) The head moves to the right until it encounters y and replaces y by 1
(q2zRq2' Z E f - {y} and q~vlq3)'
(v) On reaching the right end, the head scans b and replaces this b by
Y (q3byqJ.).
(vi) The head moves to the left until it scans the symbol b. This b is
replaced by 1 (qJ.zLqJ., Z E f - {x;}, qJ.xiLqS' q s blq6)'
(vii) The head moves to the left and one of the l' s in 1{/i is replaced by
b. M reaches q2 (q6ILq,. qilbq2)'
As a result of (i)-(vii), one of the 1's in l
a ; is replaced by band
1 is added to the left of y. Steps (iv)-(vii) are repeated for all l' s
in I"i.
(viii) On scanning Xi-I' the head moves to the right and M enters
qs (q,xi-lRqS)'
As there are no quadruples starting with qs, the Turing machine M halts.
When i :j:. 1 and ai :j:. O. the telminal ill is I"lXI ... Xi-lq81";xi ... x l1 bl
ai y.
For example, let us compute Ul(l. 2. 1):
qol.tlIl.c2Ix3by
~ Ix 1 llqox 2 1.\:3by
r- Lt 1 lq 1 Ix 2 h 3 by r- Ixllq2bx2Ix3by
~ IXllbx2Ix3bq2Y
r- Ix[lbx2Ix)7q31
r- lxIlbx2Ix3blq3b r- lXllbx2lx}blq4Y
~ Ix 1 lbq4x2Ix}bly r- Ix! Iqs bx21x}bly
r- Ixllq6Ix2Ix3blv r- lXlq711x2Ix3bly
r- b:lq2blx2Ix3blv
From the above derivation. we see that
l.Yjlq2bx2Ix3by ~ l.Ylq2bl.t21x3bIy
Repeating the above steps, we get
Ixlq2blx2lx}bl.v P- LCjqslh2Ix3blly
It should be noted that this construction is similar to that for the successor
function. While computing U/", the head skips the portion of the input
corresponding to ai. j :j:. i. For every 1 in l"i. 1 is added to the left of y.