which sim pli fies to
add
add
add
( , ( ))
( , ( )) (
( , )).
x z x
x
x s y
s
x y
=
=
As an example, add (3, 2) works as follows:
add
s(add
( ( ( ( ( )))), ( ( ( ))))
( ( ( ( ( )))),
s s s z x
s s z x
s s s z x
s( ( ))))
( (
( ( ( ( ( )))), ( )))))
( ( ( ( ( (
z x
s s
s s s z x
z x
s s s s s z
add
x)))))).
(b) Multiplication of Two Numbers: The new feature is the use of a previously
defined function, add, in the definition of a new function. We skip the step of
playing around with the p i functions to pick out the right parts, and go to the
simplified form.
multiply
multiply
add( mult
( , ( ( )))
( , ( ))
,
x s z x
x
x s y
x
=
=
iply ( , ))
x y
(c) Predecessor of a Number: The important catch here is that it will not be
able to drop below zero, so effectively 0 – 1 = 0. In order to show this, we write
a dot above the minus sign and call it “monus”. The function is easy to define:
pred
pred
( ( ))
( )
( ( ))
z x
z x
s x
x
=
=
(d) Subtraction:
subtract ( , ( ))
x z x
x
=
sub tract (x, s(y)) = pred (sub tract (x, y)).
Ì Exam ple 6.4.1: Given
g
x y x y
g
x y
xy
g
x y
x
1
2
3
3
12
=
= +
=
=
=
=
( , )
,
( , )
( , )
and h x y z x y z
( , , ) = + + are func tions over N. Obtain the com po si tion of h
with g 1 , g 2 , g 3 .
Solu tion
h f x y f x y f x y
h x y xy x
x y xy
( ( , ); ( , ); ( , ))
(
, ,
)
1
2
3
3 12
3
=
+
= + +
+ 12x.
Therefore the composition of h with g 1 , g 2 and g 3 is given by a function
f x y x y xy
x
( , )
.
= + +
+
3
12
Computability
223