Chapter 11: Computability g 335
TABLE 11.3 Representation of Quadruples
State
b
y
r = {h. 1. Xj. y},
11.4.5 CONSTRUCTION OF THE TURING MACHiNE FOR
COMPUTING-THE SUCCESSOR FUNCTION
The successor function S is defined by Sea)) = aj + 1 for all aj 2' : O. So the
initial tape expression can be taken as X = 1({lX1by (as in the case of the zero
function). At the end of the computation. we require 1([1+
1
to appear to the left
of Y. Hence we define a TM by taking
Q = {qo . .. " q9},
where P consists of
(i) qobRqo. qolbql' q(}"t!Rqc;
(ii) q1bRqj. qjlRqj. qlxjRqj. qj\'lq~
(iii) q~ lRq~. C]~byq3'
(iy) q3bLq3' q31Lq3' q3yLq3. q,X1Lq.+
(v) qJ,lLqJ,. C]J,blq).
(vi) q)lRqo.
(vii) qc;bRq6' qc;lRq6' C]fY"tjRq6' q6yu 17
(viii) q71Lq7. q7b1qs.
(ix) qsbLqs. qslLqs· qsyLqs. q8x IX jq9'
The corresponding operations can be explained as follows:
(i) If :'v.f starts from the initial lD. the head replaces the first 1 it
encounters by b. Afterwards the head moves to the right until it
encounters Y (as a result of q()lbqj. qjbRql' qllRql. qlxlRql)'
(ii) y is replaced by 1 and M enters q~. Once the end of the input tape is
reached. y is added to the next cell. M enters q3 (qjylq~. q~lRq~.
q~byq3)'
(iii) Then the head moves to the left and the state is not changed until Xl
is encountered (q3)'Lq3. q3yLq3' q3bLq3)'
(iv) On encountering Xlo the head moves to the left and 1\1 enters qJ,. Once
again the head moves to the left till the left end of the input string is
reached (q3xjLqJ,. q)LqJ,).
(v) The leftmost blank (written in point (i)) is replaced by 1 and M enters
q) ((].+blq)).
Thus at the end of operations (i)-(v). the input part remains unaffected but
the first 1 is added to the left of y.