4. What is Russel’s Paradox?
“Consider the set of all sets that do not have themselves as a
member. Is this set a member of itself?”
5. What is Godel’s proof of numbers about.
“If it is possible to prove within a formal system that the system is
consistent, then the formal system is not, in fact consistent.”
6. What are the different primitive recursive functions?
(a) Zero function
(b) Successor function
(c) Projector function
7. What is a zero function?
z x
z y
( )
( ),
=
for all x y I
, ∈
This is our “zero”, it is written as a function so we don’t have to
introduce constants into the system.
8. What is a successor function?
This function informally means x + 1. Formally, it does not return a
value.
9. What is a Projector function?
p x
x
p x y x
p x y
y
1
1
2
( )
( , )
( , )
=
=
=
These functions are a way of extracting one of the parameters and
discarding the rest.
10. What is a primitive recursive function?
A Total function f over N is primitive recursive if (a) it is any one of
the 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 so the set of initial functions.
11. What do you mean by composition of functions?
Use of function as arguments to functions represent composition of
functions.
f x y h g x y g x y
( , )
( ( , ), ( , ))
=
1
2
12. What is primitive recursion?
This is a structured “recursive routine” with the form
f x
g x
f x s y
h g x y g f x y
( , )
( )
( , ( ))
( ( , ), ( ( , )))
0
1
2
3
=
=
A primitive recursive function is formed from the functions z, s, p 1
and p 2 by using only composition and primitive recursion.
Computability
233