**MFCS (CS755N) Minor I August 30, 1997**

Maximum marks : 50

NOTE:

- 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 is computable. - 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 byThat 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 thatHere 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