3. Determine 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
( ) =
9
over
(b) f x x
N
( ) =
−
2
25 over
(c) f x
x
x
N
( ) =
+ +
3
2 5
2
over
(d) f x x
N
( ) = + 8 over .
4. Given g x y x
y g x y
xy
1
2
2
2
( , )
, ( , )
= +
=
and g x y
x
3
6
( , ) =
and
h x y z
x y z
( , , ) = + +
2
are functions over N. Obtain the composition of h
with g 1 , g 2 and g 3 .
5. Given f
x x f
1
1
2
2
2
2
2
=
=
,
λ, f
x x
3
1 2
2
=
all defined over Σ. With the pair
( , )
x y
1
1 and g x x x
x x
( , , )
1
2
3
2 3
15
=
again defined over Σ. Obtain the
composition of g with f 1 , f 2 and f 3 .
6. Show that the function f
x y xy
mult ( , ) = is primitive recursive.
7. Show that the function f(x, y) = Min (x, y) is primitive recursive.
8. Show that the function Q x y
( , ) = Quotient ( / )
x y is primitive recursive.
9. Show that the function p x
x
x
x
( )
,
,
=
−
≠
=



2 1
0
0
0
is primitive recursive.
10. Check whether the function g x y x
y
( , ) =
2
is primitive recursive or not.
11. Show that the function f x x
( )
/
= 2 is partial recursive function over N.
12. Prove that the function
f x
x
x
x
( ) =
+



4
4 1
if is perfect square
otherwise
is primitive recursive.
13. Compute A(2, 4) and A(3, 3) when A(x, y) is Ackermann’s function.
SHORT QUESTIONS AND ANSWERS
1. What are the properties of a formal system?
(a) Completeness
(b) Consistency
2. Define the term ‘completeness’ of a formal system.
It could be either to prove or disprove any proposition that can be
expressed in the system.
3. Define the term ‘consistency’ of a formal system.
It should not be possible to both prove and disprove a proposition in
the system.
232
Theory of Automata, Formal Languages and Computation