These pro jec tor func tions are a way of extract ing one of the param e ters and
dis card ing the rest. We define only P 1 and P 2 as only func tions of no more
than two argu ments are only discused.
Definition: A total function f over N is primitive recursive if (i) it is any one of
the three initial functions [zero function, successor function and Projector
Function] or (ii) it can be got by applying composition and recursion finite
number of times to the set of initial functions. This is dealt with in the
subsequent sections.
Ì Exam ple 6.3.1: How are the following functions defined.
(a) Zero function Z(x)
(b) Successor function S(x)
(c) Projection function P x
i
n ( ).
Solu tion
(a) Zero function Z(x) = 0
(b) Successor function S(x) = x + 1
(c) Projection function P x x
x
x
i
n
n
i
( , ,
)
1
2 KK
=
Ì Exam ple 6.3.2: How are the following functions defined?
(a) nil (x)
(b) cons a(x)
(c) cons b(x)
Solu tion
(a) nil (x) = λ
(b) cons a(x) = ax
(c) cons b(x) = bx
Ì Exam ple 6.3.3: Find out the values of
(a) Z( )
80
(b) P 2
4 2 3 7 6
( , , , )
(c) P 3
4 2 3 6 7
( , , , )
(d) S ( )
78
With Z as the zero function, S as the successor function and U as the
projection function.
220
Theory of Automata, Formal Languages and Computation