Next: Decidability and Partial decidability
Up: MFCS: Problem set 3
Previous: smn theorem

 Show that there is a decidable predicate Q(x,y,z) such that
 if and only iff
 if , and Q(x,y,z), then
 Deduce that there is a computable function g(x,y) such that
 g(x,y) is defined if and only if
 if , then and
; i.e.
 Deduce that if f is a computable injective function (not
necessarily total or surjective) the is computable.
 Show that there is total computable function k(e) such that for any
e, if is the characteristic function for a decidable predicate
M(x), then is the characteristic function for
.
 Show that there is a total computable function k(x) such that
for every x, .
 Show that there is a total computable function s(x,y) such that
for all x,y .
 Suppose that f(x) is computable; show that there is a total computable
function k(x) such that for all x, .
Subhashis Banerjee
Sat Sep 27 16:37:46 IST 1997