Solutions (or Hints) to Chapter-end Exercises ~ 413
11.4 (b) It is clear that rex, 0) = O. Also, rex, y) increases by 1 when y is
increased by 1 and rex, y) =0 when y =x. Using these observations we
see that rex, y + 1) = S(r (x,y)) * sgn(x -'- S(r (x, y))). Hence
rex, y) is 1 defined by
rex, 0) = 0
rex, y + 1) = S(r(x, y)) * sgn(x -'- S(r(x, y)))
11.5 I(x) is the smallest value of y for which (y + 1)2 > x. Therefore,
fix) =.uyCX[O}((y + 1)2 -' - x)), I is partial recursive since it is obtained
from primitive recursive functions by application of minimization.
11.8 The constant function I(x) = 1 is primitive recursive for 1(0) = 1 and
fix + 1) = Ul(x, fix)). Now XAc, XAnB and XA u B are recursive for
XAc = 1 -'- XA' XAnB = XA * XB and XAuB = XA + XB -'- XAnB
(Addition and proper subtraction are primitive recursive functions and
the given functions are obtained from recursive functions using
composition.)
11.9 Let E denote the set of all even numbers. XE(O) = 0, XECn + 1) =
1 -' - sgn(U}(n, XE(n)). The sign function and proper subtraction
function are primitive recursive. Thus E is obtained from primitive
recursive functions using recursion. Hence XE is primitive recursive and
hence recursive. To prove the other part use Exercise 11.8.
11.11 Define I by flO) = k, fin + 1) = U}(n, j(n)). Hence I is primitive
recurSIve.
11.12 X{{lj.a2'" .. a ll
}
= X{ad + X[a2} + ... + X{a ll
}'
As X{ad is primitive
recursive. (Refer to Exercise 11.2(a)) and the sum of primitive
recursive functions is primitive recursive, X{ar, a2, ..., all} is primitive
recursive.
11.13 Represent x and y in tally notation. Using Example 9.6 we can compute
concatenation of strings representing x and y which is precisely x + y
in tally notation.
11.14 Let M in the Post notation have {qj, q2,
, qll} and {at> a2, ..., am}
as Q and L respectively. Let Q' = {qj, , qll' qll+j, ..., q21l}, where
qll+l ..., q211 are new states. Let a quadruple of the form qiajRqk induce
the quintuple qiapkRqk' Let a quadruple of the form qia/-LJk induce the
quintuple q;apjLqk' Finally, let qiapkq, induce qiapkRqll+i' We
introduce quintuples qll+iafltLqi for i = 1, 2, ..., nand t = 1, 2, 3,
..., m. The required TM has Q' as the set of states and the set of
quintuples represent 8.