Ì Exam ple: Given f
x x f
f
x x
1
1
2
2
2
2
3
1 2
5
=
=
=
,
,
λ
all defined over Σ
with the pair (x 1 , y 1 ) and g(x 1 , x 2 , x 3 ) = 5x 2 x 3 ; again defined over Σ. Obtain
the composition of g with f 1 , f 2 and f 3 .
Solu tion
g f f f
g x x
x x
x x
x x
( , , )
(
, ,
)
(
)
.
1
2
3
1
2
2
2
1 2
1 2
1 2
5
5 5
25
=
=
=
λ
λ
Therefore the composition of g with f 1 , f 2 and f 3 is given by
h x x
x x
( , )
.
1
2
1 2
25
=
Ì Exam ple 6.4.2: Prove that the function f
x y x y
add ( , ) = + is primitive
recursive.
Solu tion
A function f of (n + 1) variables is defined by recursion if there exists a
function g of ‘n’ variables, and a function h of (n + 2) variables and f is defined
as follows:
f x x
x
g x x
x
n
n
( , ,
, )
( , ,
)
1
2
1
2
0
KK
KK
=
(1)
f x x
x y
g x x
x y f x x
x y
n
n
n
( , ,
,
)
( , ,
, , ( , ,
, ))
1
2
1
2
1
2
1
KK
KK
KK
+ =
(2)
f
x y
add ( , ) is a function of two variables. In order that f
x y
add ( , ) is defined by
recursion, we require a function ‘g’ of a single variable and a function ‘h’ of
three variables.
f
x
x
x
add ( , )
0
0
= + =
(3)
Comparing f
x
add ( , )
0 with the left hand side of (1), we have
g x x p x
( )
( )
= = ′
1
(4)
(Note that p is the projector function).
Also we have
f
x y
x
y
x y
f
x y
add
add
( ,
)
(
) (
)
( , )
+ = + + = + + =
+
1
1
1
1
(5)
Com paring this with L.H.S. of equa tion (2), we have
h x y f x y
f
x y
s f
x y
s p x y f
( , , ( , ))
( , )
(
( , ))
( ( , ,
=
+
=
=
add
add
1
3
3
add ( , )))
x y
Let us assume h x y z s p x y z
( , , ) ( ( , , )).
=
3
3
224
Theory of Automata, Formal Languages and Computation