344 i;1. Theory ofComputer Science
g
if x> v
(f) L(x. ,) =
if x :S y
(1 if x = v
(g) Eer, v) = to if x *- v
11.3 Compute A(3, 2). A(2, 3), A(3, 3).
11.4 Show that the following functions are primitive recursive:
(a) q(x. y) = the quotient obtained when x is divided by y
(b) rex, y) = the remainder obtained when x is divided by y
{
2X
if x is a perfect square
(c) f(x) =
2x + 1
otherwise
11.5 Show that f(x) = integral part of j; is patti'll recursive.
11.6 Show that the Fibonacci numbers are generated by a primitive recursive
function.
11.7 Let f(O) = 1, f(l) = 2, f(2) = 3 and f(x + 3) = f(x) + f(x + 1)1 +
fi.'( + 2)3. Shovv that f(:r) is primitive recursive.
11.8 The characteristic function XA of a given set A is defined as
ra if a ~ A
x\(a) = ~
II if a E A
If A, B are subsets of Nand XAo XB are recursive, show that X/, XAuB,
Xv. . B are also recursive.
11.9 Show that the characteristic function of the set of all even numbers is
recursive. Prove that the characteristic function of the set of all odd
integers is recursive.
11.10 Show that the function lex. .1') = x - v is partial recursive.
11.11 Show that a constant function over N. i.e. fen) =k for all n in N where
k is a fixed number. is primitive recursive.
11.12 Show that the characteristic function of a finite subset of N is primitive
recurSIve.
11.13 Show that the addition function fl (x, y) is Turing-computable.
(Represent x and v in tally notation and use concatenation.)
11.14 Show that the Tming machine 1' v1 in the Post notation (i.e. the transition
function specified by quadruples) can be simulated by a Turing
machine Iv! (as defined in Chapter 9).
[Hint: The transition given by a quadruple can be simulated by two
quintuples of i'v1' by adding new states to M~]