Primitive Recursive function: Total function is primitive recursive if (a) it is
any one of three initial functions (zero function, successor function and
Projector function) or (b) it can be got by applying composition and
recursion finite number of times to the set of initial functions.
Initial functions: Zero function, successor function and projector function.
Composition of functions: Allows us to use functions as arguments to
functions.
f x y h g x y g x y
( , )
( ( , ), ( , ))
=
1
2
Ackermann’s function:
A y
y
A x
A x
A x y
A x
A x y
( , )
( , )
(
, )
( , )
(
, ( ,
))
0
1
0
11
1
1
= +
=
−
=
−
−
REVIEW QUESTIONS
1. What are formal systems?
2. Define (a) Completeness (b) Consistency in Formal Systems.
3. State the Russel’s Paradox.
4. What are recursive functions?
5. Give examples for recursive functions.
6. What is a primitive recursive function?
7. Give examples for primitive recursive function.
8. Explain composition of functions.
9. What do you mean by primitive recursion?
10. What is Ackermann’s function?
EXERCISES
1. Obtain the values of
(a) Z(90)
(b) p 2
5 2 3 7 8 6
( , , , , )
(c) p 3
7 1 2 3 4 5 6 7
( , , , , , , )
(d) S(82).
2. Obtain the values of
(a) nil (abababab)
(b) cons a(ababab)
(c) cons b(abababa)
Computability
231