next up previous
Next: About this document

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 tex2html_wrap_inline54 is computable.
  2. Let tex2html_wrap_inline56 be an enumeration of partial functions from tex2html_wrap_inline58 to tex2html_wrap_inline58 . Construct a function tex2html_wrap_inline62 such that tex2html_wrap_inline64 for each i.
  3. Find a unary primitive recursive function f, such that for each tex2html_wrap_inline70 , f(n) is the index of the function tex2html_wrap_inline74 . Here tex2html_wrap_inline74 denotes the greatest natural number at most equal to the tex2html_wrap_inline78 root of x.
  4. Suppose that f is a unary primitive recursive function. Define tex2html_wrap_inline84 by

    displaymath48

    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 tex2html_wrap_inline98 , there is a total computable (m+1)-ary computable function tex2html_wrap_inline102 such that

    displaymath49

    Here tex2html_wrap_inline104 and tex2html_wrap_inline106 . You may use the simple form of the s-m-n theorem (done in the class) to prove this.

  6. Prove that ` tex2html_wrap_inline110 is total' is undecidable.


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