Solu tion
Given
f x
x y
y x
y
( )
( , )
( — )
=
= +
•
Max
where —
•
represents “Monus” given by
pred
pred
( ( ))
( )
( ( ))
z x
z x
s x
x
=
=



.
Therefore the given function f (x, y) is primitive recursive.
Ì Exam ple 6.4.6: Prove that the function R(x, y) = Remainder (x/y) is
primitive recursive.
Solu tion
When y = 0, R(x, y) = R(x, 0) = 0. When y is increased in its value by 1, the
remainder R(x, y) also increases by 1.
When y = x, we have R(x, y) = 0.
Therefore we have
R x y
s R x y
x s R x y
( ,
) ( ( , )) * sgn (
( ( , ))).
+ =
•
1
—
where s is the successor function,—
•
represents the monus function (defined in
the usual way) and sgn (x) represents the signum function.
Therefore we have the remainder function defined by
R x
R x y
s r x y
x s R x y
( , )
( ,
)
( ( , )) * sgn (
( ( , ))).
0 0
1
=
+ =
•
—
Hence the function R x y
( , ) = Remainder (x / y) is primitive recursive, as it
obtained by applying composition and recursion to known primitive functions.
Ì Exam ple 6.4.7: Show that the characteristic function χ { } ( )
0 x defined by
χ { } ( )
,
,
0
0
0
1
0
x
x
x
=
≠
=



is primitive recursive.
Solu tion
Given the characteristic function
226
Theory of Automata, Formal Languages and Computation