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

 Use a direct diagonal construction to show that the
problem ` is undecidable.
 Show that the problem ` ' is undecidable by
reducing ` is total' to this problem.
 Prove that a partial function f is computable if and only if
the predicate is partially decidable.
 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?
 Use RiceShapiro's theorem to show that the following problems are not
partially decidable:
 ` '
 ` '
 ` '
Subhashis Banerjee
Thu Oct 2 10:40:07 IST 1997