Chapter 11: Computability ~ 343
9. U 2 '+C5(4), 5(5), 5(6), Z(7)) IS
(a) 6
(b) 5
(c) 4
(d) 0
10. If g(x, y) = min(x, y) and hex, y) = Ix - y I. then:
(a) Both functions are regular functions.
(b) The first function is regular and the second is not regular.
(c) Neither of the functions is regular.
(d) The second function is not regular.
State whether the Statements 11-15 are true or false.
11. f(x, y) = x + y is primitive recursive.
12. 3 -=- 4 = O.
13. The transpose function is not primitive recursive.
14. The Ackermann's function is recursive but not primitive recursive.
15. A(2, 2) = 7.
EXERCISES
11.1 Test which of the following functions are total. If a function is not
total. specify the arguments for which the function is defined.
(a) f(x) = x/3 over N
(b) fex) = 1/(x - 1) over N
(c) f(x) = _~ - 4 over N
(d) f(x) = x + lover N
(e) f(x) =rover N
11.2 Show that the following functions are primitive recursive:
r1 if x =0
(a) X{Oj(x) = ~
lO if x "# 0
(b) f(x) = r
(c) f(x, y) = maximum of x and y
{
X/2
when x is even
(d) f(x) =
(x - 1)/2 when x is odd
(e) The sign function defined by
sgn(O) = 0,
sgn(x) = 1
if
x> O.