Chapter 11: Computability J;;t 339
(ii) The tape expression obtained at the end of (i) is
The construction given in (i) is repeated. i.e. M simulates M 2 • .•.• M k ,
changes y to x;, and adds by to the right of x;. After simulating Mk>
the tape expression is
X' = I"IXl ... I"mx m 1 bt x'l ... 1bk-lXk_tlbkx'k by
Then the head moves to the left until it is positioned at the cell having
1 just to the right of x m .
(iii) M simulates M k + 1 • M k + 1 with initial tape expression X' halts with the
tape expression Iblx'i ... Ibkx;" 1'y. As a result, the corresponding tape
expression for M is obtained as
·1"1.- I"2x
1"",.- 1 b1 ,J
Ibh-' Ii'v
., 1
2' . .
"",
A I ' "
., k ~
(iv) The required value is obtained to the left of y. but I
b tx'l ... Ihkx'k also
appears to the left of c. M erases all these symbols and moves Iiy just
to the right of XIII' The head moves to the cell having x", and M halts.
The final tape expression is 1"lxJI"2x2 ... 1" m x m I(y.
11.4.8 CONSTRUCTION OF THE TURING MACHINE THAT
CAN PERFORM RECURSION
Let g(XI' .... x",). h(Yl' 1'2, .... Ym.d be Turing-computable. Let f(x[o ...,
X m +1) be defined by recursion as follows:
f(XI' .... X m • 0) = g(x] ... XII,)
f(x) . ... , x"', I' + 1) = h(xio ... , x m , y, f(xJ' ..., Xm' Y»
For the Turing machine Ai, computing f(a1o .... am, c), (say k), X IS
taken as
As the construction is similar to the construction for computing
composition. \ve outline below the steps of the construction.
Step 1 Let l'vf simulate the Turing machine M' which computes g(at, ..., am)'
The computed value, namely g(a)
, all,). is placed to the left of y. If
c = O. then the computed yalue g(a]
, a,/i) is f(a]- .... am, 0). The head
is placed to the right of Xl/! and M halts.
Step 2 If c is not equal to zero, lito the left of Xm+1 is replaced by bi. The
marker Y is changed to X m +2 and bv is added to the right of X",+2' The head
moves to the left of 1"1.
Step 3 h is computable. M is allowed to compute h for the arguments at •... ,
a",_ O. g(at . ... , am) \vhich appear to the left of XJ' . . . , x m ' X m +1o XII/+2,
(ii) The tape expression obtained at the end of (i) is
The construction given in (i) is repeated. i.e. M simulates M 2 • .•.• M k ,
changes y to x;, and adds by to the right of x;. After simulating Mk>
the tape expression is
X' = I"IXl ... I"mx m 1 bt x'l ... 1bk-lXk_tlbkx'k by
Then the head moves to the left until it is positioned at the cell having
1 just to the right of x m .
(iii) M simulates M k + 1 • M k + 1 with initial tape expression X' halts with the
tape expression Iblx'i ... Ibkx;" 1'y. As a result, the corresponding tape
expression for M is obtained as
·1"1.- I"2x
1"",.- 1 b1 ,J
Ibh-' Ii'v
., 1
2' . .
"",
A I ' "
., k ~
(iv) The required value is obtained to the left of y. but I
b tx'l ... Ihkx'k also
appears to the left of c. M erases all these symbols and moves Iiy just
to the right of XIII' The head moves to the cell having x", and M halts.
The final tape expression is 1"lxJI"2x2 ... 1" m x m I(y.
11.4.8 CONSTRUCTION OF THE TURING MACHINE THAT
CAN PERFORM RECURSION
Let g(XI' .... x",). h(Yl' 1'2, .... Ym.d be Turing-computable. Let f(x[o ...,
X m +1) be defined by recursion as follows:
f(XI' .... X m • 0) = g(x] ... XII,)
f(x) . ... , x"', I' + 1) = h(xio ... , x m , y, f(xJ' ..., Xm' Y»
For the Turing machine Ai, computing f(a1o .... am, c), (say k), X IS
taken as
As the construction is similar to the construction for computing
composition. \ve outline below the steps of the construction.
Step 1 Let l'vf simulate the Turing machine M' which computes g(at, ..., am)'
The computed value, namely g(a)
, all,). is placed to the left of y. If
c = O. then the computed yalue g(a]
, a,/i) is f(a]- .... am, 0). The head
is placed to the right of Xl/! and M halts.
Step 2 If c is not equal to zero, lito the left of Xm+1 is replaced by bi. The
marker Y is changed to X m +2 and bv is added to the right of X",+2' The head
moves to the left of 1"1.
Step 3 h is computable. M is allowed to compute h for the arguments at •... ,
a",_ O. g(at . ... , am) \vhich appear to the left of XJ' . . . , x m ' X m +1o XII/+2,