   # Minor 1

MFCS (CS755N) Minor I August 30, 1997
Maximum marks : 50

NOTE:

1. Notations are standard (as done in the class).
2. You may use any result done in the class.
3. Q1 and Q2 are 5 marks each. Q3 to Q6 are 10 marks each.

1. Suppose that f(x) is a total injective computable function; prove that is computable.
2. Let be an enumeration of partial functions from to . Construct a function such that for each i.
3. 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.
4. Suppose that f is a unary primitive recursive function. Define by That is, F(0) =0, F(1) = f(1), F(2) = f(f(2)), and so on. Show that F is primitive recursive.

5. 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.

6. Prove that ` is total' is undecidable.

Subhashis Banerjee
Fri Sep 5 15:51:01 IST 1997