From (4) we have
g p x
= ′
1 ( ).
Therefore we have h that is got from the initial functions p 3
3 and s by
composition and f add is got by recusion using g and h.
Hence we see here that f add is got by applying composition and recursion
finite number of times to initial functions p p
1
1
3
3
,
and s.
Therefore f
x y x y
add ( , ) = + is “primitive recursive”.
Ì Exam ple 6.4.3: Show that the function f x x
( ) =
2 is primitive
recursive.
Solu tion
Given f (x) = x
2 .
f x
x
x
x
f x s s z x
p x s z
(
) (
)
( ) ( ( ( ))))
( ) ( (
+ = +
=
+ +
=
+
⋅ ′
+
1
1
2 1
2
2
1
x)).
Thus we have f (x) shown to be obtained by recursion and addition of primitive
recursive functions.
Ì Exam ple 6.4.4: Prove that the function given by the signum function
sgn( )
,
,
x
x
x
=
=
>



0
0
1
0
is primitive recursive.
Solu tion
Given that the signum function
sgn( )
,
,
x
x
x
=
=
>



0
0
1
0
Now,
sgn( )
( )
sgn(
)
( ( ( , sgn( ))))
0
0
1
2
2
=
+ =
z
x
s z p x
x
Therefore the given signum function is primitive recursive.
Ì Exam ple 6.4.5: Prove that the function
f x y
x y
( , )
( , )
= max
is primitive recursive.
Computability
225