Next: About this document
MFCS (CS755N) Minor I August 30, 1997
Maximum marks : 50
- Notations are standard (as done in the class).
- You may use any result done in the class.
- Q1 and Q2 are 5 marks each. Q3 to Q6 are 10 marks each.
- Suppose that f(x) is a total injective computable function; prove that
- Let be an enumeration of partial functions
from to . Construct a function such
that for each i.
- Find a unary primitive recursive function f, such that for each
, f(n) is the index of the function . Here
denotes the greatest natural number at most equal to
the root of x.
- Suppose that f is a unary primitive recursive function. Define
That is, F(0) =0, F(1) = f(1), F(2) = f(f(2)), and so on. Show
that F is primitive recursive.
- Prove the general version of s-m-n theorem which says that:
The s-m-n theorem: For each , there is a total
computable (m+1)-ary computable function such that
Here and .
You may use the simple form of the s-m-n theorem (done in the class)
to prove this.
- Prove that ` is total' is undecidable.
Fri Sep 5 15:51:01 IST 1997