MFCS (CS755N) Minor II October 1, 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 of 10 marks each. Q3 and Q4 are of 15 marks each.

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

• About this document ...