338 ~ Theory ofComputer Science
Thus we have shown that the three initial primitive recursive functions are
Turing-computable. Next we construct Turing machines that can perform
composition, recursion. and minimization.
11 .4.7 CONSTRUCTION OF THE TURING MACHINE THAT
CAN PERFORM COMPOSITION
Let fIC-'l' X.2' ..., .\,,)•...• fiJxI, .... XIII) be Turing-computable functions. Let
g(YI' .. " YI.) be Turing-computable. Let h("I, ... , XIII) = g(fl(XI ...• x m ) .•••
.MXi' . , ., XIII»' We construct a Turing machine that can compute h(aj, ...• am)
for given arguments aj, .... am' This involves the following steps:
Step 1 Construct Turing machines All' .... M k which can compute fl' ... , .I;.
respectively. For the TMs Mj, .... lvII.:' let T' = {I, b, Xl. X.:; • .... x n , y} and
X = 1°1,]
1
0m X in by. But the number of states for these TMs will vary.
Let 111 + 1.
11k + 1 be the number of states for /\.1 1 , .... A'h. respectively.
As usuaL the initial state is (jo and the states for M i are qQ, ... , q,,;, As in the
earlier constructions. the set Pi of quadruples for M i is constructed in such a
way that there is no quadruple starting with ql1;'
Step 2 Let f;(ai' ..., am) = b i for i = 1. 2, ..., k. At the end of step 1,
we have M;'s and the computed values bi's. As g is Turing-computable. we
can construct a TM A'h+l which can compute g(b] • .... b k )· For M k + l •
X , - I hl .'
1 0m ' l .
-
X \ •••
X III 7)
(\Ve use different markers for M k + 1 so that the TM computing h to be
constructed need not scan the inputs a] . ... , am') Let I1k+\ + 1 be the number
of states of M k +]. As in the earlier constructions, M k + 1 has no quadruples
starting with qk+ I'
Step 3 At the end of step 2. we have TMs M I , ... , M b lvh+1 which give
b l . . . . . bin and g(b] . .... bJ = c (say). respectively. So we are able to
compute h(al' .... am) using k + 1 Turing machines. Our objective is to
construct a single TM kh+.2 which can compute heal' ..., an,). We outline the
construction of M without giving the complete details of the encoding
mechanism. For M. let
T' = {1. b, Xi' " .. X"I' x'\.
(1) In the beginning, lv! simulates Mj • As a result. the value b j =
fi(al' ... , am) is obtained as output. Thus we get the tape expression
1°\x I 1!!2x. :; ... 1(1mx m l bl y which is the same as that obtained by M 1
while halting. lv! does not halt but cbanges y to x'] and adds by to the
right of X'I' The head moves to the left to reach the beginning of X.
Thus we have shown that the three initial primitive recursive functions are
Turing-computable. Next we construct Turing machines that can perform
composition, recursion. and minimization.
11 .4.7 CONSTRUCTION OF THE TURING MACHINE THAT
CAN PERFORM COMPOSITION
Let fIC-'l' X.2' ..., .\,,)•...• fiJxI, .... XIII) be Turing-computable functions. Let
g(YI' .. " YI.) be Turing-computable. Let h("I, ... , XIII) = g(fl(XI ...• x m ) .•••
.MXi' . , ., XIII»' We construct a Turing machine that can compute h(aj, ...• am)
for given arguments aj, .... am' This involves the following steps:
Step 1 Construct Turing machines All' .... M k which can compute fl' ... , .I;.
respectively. For the TMs Mj, .... lvII.:' let T' = {I, b, Xl. X.:; • .... x n , y} and
X = 1°1,]
1
0m X in by. But the number of states for these TMs will vary.
Let 111 + 1.
11k + 1 be the number of states for /\.1 1 , .... A'h. respectively.
As usuaL the initial state is (jo and the states for M i are qQ, ... , q,,;, As in the
earlier constructions. the set Pi of quadruples for M i is constructed in such a
way that there is no quadruple starting with ql1;'
Step 2 Let f;(ai' ..., am) = b i for i = 1. 2, ..., k. At the end of step 1,
we have M;'s and the computed values bi's. As g is Turing-computable. we
can construct a TM A'h+l which can compute g(b] • .... b k )· For M k + l •
X , - I hl .'
1 0m ' l .
-
X \ •••
X III 7)
(\Ve use different markers for M k + 1 so that the TM computing h to be
constructed need not scan the inputs a] . ... , am') Let I1k+\ + 1 be the number
of states of M k +]. As in the earlier constructions, M k + 1 has no quadruples
starting with qk+ I'
Step 3 At the end of step 2. we have TMs M I , ... , M b lvh+1 which give
b l . . . . . bin and g(b] . .... bJ = c (say). respectively. So we are able to
compute h(al' .... am) using k + 1 Turing machines. Our objective is to
construct a single TM kh+.2 which can compute heal' ..., an,). We outline the
construction of M without giving the complete details of the encoding
mechanism. For M. let
T' = {1. b, Xi' " .. X"I' x'\.
(1) In the beginning, lv! simulates Mj • As a result. the value b j =
fi(al' ... , am) is obtained as output. Thus we get the tape expression
1°\x I 1!!2x. :; ... 1(1mx m l bl y which is the same as that obtained by M 1
while halting. lv! does not halt but cbanges y to x'] and adds by to the
right of X'I' The head moves to the left to reach the beginning of X.