next up previous
Next: About this document

MFCS (CS755N) Minor II October 1, 1997
Maximum marks : 50


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

    1. Use a direct diagonal construction to show that the problem ` tex2html_wrap_inline30 is undecidable.
    2. Show that the problem ` tex2html_wrap_inline32 ' is undecidable by reducing ` tex2html_wrap_inline34 is total' to this problem.
  1. Prove that a partial function f is computable if and only if the predicate tex2html_wrap_inline38 is partially decidable.
  2. Suppose that f is a total computable function, A is a recursive set and B is a recursively enumerable set. Show that tex2html_wrap_inline46 is recursive and that f(A), f(B) and tex2html_wrap_inline52 are recursively enumerable but not necessarily recursive. What extra information can be obtained about these sets if f is a bijection?
  3. Use Rice-Shapiro's theorem to show that the following problems are not partially decidable:
    1. ` tex2html_wrap_inline56 '
    2. ` tex2html_wrap_inline58 '
    3. ` tex2html_wrap_inline60 '

Subhashis Banerjee
Thu Oct 2 10:40:07 IST 1997