Solu tion
(a) Z( )
80 0
= since zero function Z x
( ) .
= 0
(b) We know that P x x
x
x
i
n
n
i
( , ,
, )
.
1
2 KK
=
Therefore we have
P 2
4 2 3 7 6 3
( , , , ) =
(c) P 3
4 2 3 6 7 6
( , , , ) =
(d) S x x
( ) = + 1.
Therefore S(78) = 78 + 1 = 79.
Ì Exam ple 6.3.4: Obtain the values of
(a) nil (ababab)
(b) cons a(baba)
(c) cons b(ababab)
with the usual definitions of functions over Σ.
Solu tion
(a) nil (ababab) = λ
(b) cons a(baba) = ababa
(c) cons b(ababab) = bababab.
Ì Exam ple 6.3.5: Check whether the following functions are Total
functions or not. If a function is not total, specify the arguments for which
the function is defined.
(a) f x x
N
( ) = 4over
(b) f x x
N
( ) =
−
2
9 over
(c) f x x
N
( ) = + 4 over
(d) f x x
N
( ) =
2 over
(e) f x
x
x
N
( ) =
+
+
5
2
6
3
2
over .
Solu tion
(a) f x x
N
( ) = 4over .
The function is defined for all natural numbers divisible by 4.
(b) f x x
N
( ) =
−
2
9 over .
The function is defined for all x ≥ 3.
(c) f x x
N
( ) = + 4 over .
The function is defined for all natural numbers.
Computability
221