next up previous
Next: About this document

Minor II Solutions

    1. Construct

      displaymath76

      g is computable if tex2html_wrap_inline86 is decidable. Clearly, Range of g is different from that of every computable function. Let tex2html_wrap_inline90 . Then

      eqnarray19

      Thus we have a contradiction.

    2. Suppose tex2html_wrap_inline92 is decidable. Then so is tex2html_wrap_inline94 . But tex2html_wrap_inline96 .
  1. Suppose that f is computable. Then there is a program P that computes it. We have that

    displaymath77

    The predicate on the RHS is partially decidable by Theorem done in the class.

    Conversely, suppose that the predicate tex2html_wrap_inline104 is partially decidable. Let tex2html_wrap_inline106 be a decidable predicate such that

    displaymath78

    Then we have the following algorithm for computing f. Search for a pair of numbers y,t such that tex2html_wrap_inline106 holds; if and when such a pair is found then tex2html_wrap_inline114 . Hence f is computable. [Note that in the usual way a search over y,t can be conducted by coding the pair as a single number tex2html_wrap_inline120 .]

  2. Given that f is a total computable function, A is a recursive set and B is a recursively enumerable set.

    Now, tex2html_wrap_inline128 ; since f is total computable, f(x) is defined and tex2html_wrap_inline134 is decidable because A is recursive. We have that tex2html_wrap_inline138 . Hence tex2html_wrap_inline140 is recursive.

    f(A) and f(B) are ranges of a total unary computable function. Hence these sets are recursively enumerable. However, f is not necessarily a total increasing computable function; consequently, f(A) and f(B) are not necessarily recursive.

    Now, B is recursively enumerable. Hence it is the range of a total unary computable function, say g. Now, tex2html_wrap_inline156 . Now since both f and g are total computable, the predicate `f(x) = g(y)' is decidable. Thus tex2html_wrap_inline164 is partially decidable, which in turn implies that tex2html_wrap_inline166 is recursively enumerable. This set is recursive only if g is increasing.

    If f is a bijection then tex2html_wrap_inline172 is also total computable but not necessarily monotonic. Thus tex2html_wrap_inline174 '. Since A is recursive so is f(A). But since neither f nor tex2html_wrap_inline172 are monotonic f(B) and tex2html_wrap_inline166 are not necessarily recursive.

    1. Define tex2html_wrap_inline188 .

      Let this set be r.e. If this set is r.e. then according to Rice-Shapiro's theorem: `if there exists a finite tex2html_wrap_inline190 , tex2html_wrap_inline192 for some computable f, then tex2html_wrap_inline196 '.

      Let f be a total computable function. Clearly tex2html_wrap_inline200 . Let tex2html_wrap_inline202 be the function which is nowhere defined. Clearly tex2html_wrap_inline202 is of finite domain and trivially tex2html_wrap_inline192 . Also tex2html_wrap_inline190 . Thus we have a contradiction.

    2. Define tex2html_wrap_inline210 .

      Let this set be r.e. If this set is r.e. then according to Rice-Shapiro's theorem: `if there exists a finite tex2html_wrap_inline190 , tex2html_wrap_inline192 for some computable f, then tex2html_wrap_inline196 '.

      Let f be a total computable function. Let tex2html_wrap_inline202 be any finite restriction of f. Clearly tex2html_wrap_inline190 and tex2html_wrap_inline200 . Thus we have a contradiction.

    3. Define tex2html_wrap_inline230 .

      Let this set be r.e. If this set is r.e. then according to Rice-Shapiro's theorem: `if tex2html_wrap_inline196 then there must exist a finite tex2html_wrap_inline192 such that tex2html_wrap_inline190 '.

      But no finite function can be the function tex2html_wrap_inline238 . Thus we have a contradiction.




next up previous
Next: About this document

Subhashis Banerjee
Fri Nov 21 09:25:55 IST 1997