334 ~ Theory of Computer Science
N for given arguments a], .... am' Initially, the input OJ, a2' ..., am appears
on the input tape separated by markers Xj, . . . , Xlii' The computed value
f(a] , ..., am)' say, c appears on the input tape, once the computation is over.
To locate c ,ve need another marker. say y. The value c appears to the right
of X m and to the left of v. To make the construction simpler, we use the tally
notation to represent the elements of N. In the tally notation, 0 is represented
by a string of b's. A positive integer n is represented by a string consisting
of II 1's. So the initial tape expression takes the form 1"lx,1{/2x: ... 1{/mxmby.
As a resulr of computation, the initial ID qOFtxll"2X2 ... l{/lI/x lII by is changed
to a terminal ID of the form 1{/lXl1{/2X: ... 11lmx",1'q'y for some q' E Q. In
fact, the position of q' in a tenninal ID is immaterial and it can appear
anywhere in Res(X). The computed value is found between XIII and y.
Sometimes we may have to omit the leading b's.
We say that a function f(x] . ..., x",) is Turing-computable for arguments
aj, .... (1m if there exists a Turing machine for which
where ID II is a terminal ID containing f(al' ..., alii) to the left of y.
Our ultimate aim is to prove that partial recursive functions are Turingcomputable. For this purpose. first of all we prove that the three initial primitive
recursive functions are Turing-computable.
11.4.4 CONSTRUCTION OF THE TURING MACHINE THAT
CAN COMPUTE THE ZERO FUNCTION Z
The zero function Z is defined as Zeal) = 0 for all al :::: O. So the initial tape
expression can be taken as X = 11l'x l by. As we require the computed value
Zeal)' namely O. to appear to the left of y, we require the machine to halt
without changing the input. (Note that 0 IS represented by b in the tally
notation.)
Thus we define a TM by taking Q = {qo, qd, r = {b. LXI_ Y},
X = l"jx,by. P consists of qobRqo, q o lRqo. q(~llx1ql' qobRqo and q o lRqo are
used to move to the right until Xl is encountered. q~llx1ql enables the TM to
enter the state ql' M enters qj without altering the tape symbol. In terms of
change of IDs. we have
a l"lx by f.2- l"la-l i bv L- l"I('IX by
10
I . ;
1(} . . I
1. , .
As there is no quadruple starting with ql' M halts and Res(X) = 11Ij(11X1by.
By deleting ql in Res(X), we get l"lxlby (which is the same as X) yielding 0
(given by b).
Note: We can also represent the quadruples in a tabular form which is
similar to the transition table obtained in Chapter 9. In this case we have to
specify (i) the new symbol written. or (ii) the movement to the left (denoted
by L/. or (iii) the movement to the right (denoted by R). So we get
Table 11.3.
N for given arguments a], .... am' Initially, the input OJ, a2' ..., am appears
on the input tape separated by markers Xj, . . . , Xlii' The computed value
f(a] , ..., am)' say, c appears on the input tape, once the computation is over.
To locate c ,ve need another marker. say y. The value c appears to the right
of X m and to the left of v. To make the construction simpler, we use the tally
notation to represent the elements of N. In the tally notation, 0 is represented
by a string of b's. A positive integer n is represented by a string consisting
of II 1's. So the initial tape expression takes the form 1"lx,1{/2x: ... 1{/mxmby.
As a resulr of computation, the initial ID qOFtxll"2X2 ... l{/lI/x lII by is changed
to a terminal ID of the form 1{/lXl1{/2X: ... 11lmx",1'q'y for some q' E Q. In
fact, the position of q' in a tenninal ID is immaterial and it can appear
anywhere in Res(X). The computed value is found between XIII and y.
Sometimes we may have to omit the leading b's.
We say that a function f(x] . ..., x",) is Turing-computable for arguments
aj, .... (1m if there exists a Turing machine for which
where ID II is a terminal ID containing f(al' ..., alii) to the left of y.
Our ultimate aim is to prove that partial recursive functions are Turingcomputable. For this purpose. first of all we prove that the three initial primitive
recursive functions are Turing-computable.
11.4.4 CONSTRUCTION OF THE TURING MACHINE THAT
CAN COMPUTE THE ZERO FUNCTION Z
The zero function Z is defined as Zeal) = 0 for all al :::: O. So the initial tape
expression can be taken as X = 11l'x l by. As we require the computed value
Zeal)' namely O. to appear to the left of y, we require the machine to halt
without changing the input. (Note that 0 IS represented by b in the tally
notation.)
Thus we define a TM by taking Q = {qo, qd, r = {b. LXI_ Y},
X = l"jx,by. P consists of qobRqo, q o lRqo. q(~llx1ql' qobRqo and q o lRqo are
used to move to the right until Xl is encountered. q~llx1ql enables the TM to
enter the state ql' M enters qj without altering the tape symbol. In terms of
change of IDs. we have
a l"lx by f.2- l"la-l i bv L- l"I('IX by
10
I . ;
1(} . . I
1. , .
As there is no quadruple starting with ql' M halts and Res(X) = 11Ij(11X1by.
By deleting ql in Res(X), we get l"lxlby (which is the same as X) yielding 0
(given by b).
Note: We can also represent the quadruples in a tabular form which is
similar to the transition table obtained in Chapter 9. In this case we have to
specify (i) the new symbol written. or (ii) the movement to the left (denoted
by L/. or (iii) the movement to the right (denoted by R). So we get
Table 11.3.