χ { } ( )
,
,
0
0
0
1
0
x
x
x
=
≠
=



i.e.
χ
χ
χ
{ }
{ }
{ }
( )
(
)
sgn( ( ))
0
0
0
0 1
1
=
+ =
x
p x
R
where pre de ces sor func tion p x
R ( ) is given by
p x
x
x
x
R ( )
,
,
=
−
≠
=



1
0
0
0
Since we are able to represent the function as a combination of the primitive
functions, it is proved to be primitive recursive.
Ì Exam ple 6.4.8: Show that the function p R (x), the predecessor function
given by
p x
x
x
x
R ( )
,
,
=
−
≠
=



1
0
0
0
is primitive recursive.
Solu tion
Given the predecessor function
p x
x
x
x
R ( )
,
,
=
−
≠
=



1
0
0
0
We have
p
p y
p y p y
R
R
R
( )
(
)
( , ( ))
0 0
1
1
2
=
+ =
(Note: p R represents predecessor function and p 1
2 represents projector
function).
Thus the given predecessor function p x
R ( ) is defined by recursion using
an initial function (projector function).
Hence we have the function to be primitive recursive.
Ì Exam ple 6.4.9: Prove that the function
g x y x
y
( , ) =
is primitive recursive.
Computability
227