Solu tion
Given g x y x
y
( , )
.
=
We have g x y
g x
x
y
( , )|
( , )
.
= =
=
=
0
0
0
1
and
g x y
x g x y
p x y g x y p x y g x y
( ,
)
( , )
( , , ( , ) * ( , , ( , ))
+ = ⋅
=
1
1
3
3
3
Thus we have been able to represent the given function as a combination of
initial function. Therefore the given function is primitive recursive.
Ì Exam ple 6.4.10: Show that the function given by
Abs ( )
,
,
x
x x
x x
=
≥
−
<



0
0
is primitive recursive.
Solu tion
Given the absolute value function as
Abs ( )
,
,
x
x x
x x
=
≥
−
<



0
0
We are able to write
Abs (
) ( — ) ( — )
x y
x
y
y x
− =
+
•
•
Hence the function is primitive recursive as we have been able to represent the
Absolute function as a combination of initial function/or function (monus)
defined in terms of initial function.
Ì Exam ple 6.4.11: Prove that the characteristic function of a finite subset
of N is primitive recursive.
Solu tion
Let us initially prove that the characteristic function
χ { } ( )
,
,
0
0
0
1
0
x
x
x
=
≠
=



is primitive recursive.
228
Theory of Automata, Formal Languages and Computation