next up previous
Next: Recursive and recursively enumerable Up: MFCS: Problem set 3 Previous: Universal programs and universal

Decidability and Partial decidability

  1. Solve the problems of Assignment-2 using Rice's theorem.
  2. Show that the following predicates are partially decidable:
    1. ` tex2html_wrap_inline267 (n fixed).
    2. ` tex2html_wrap_inline271 is a perfect square'.
    3. `n is a Fermat's number'. (we say the n is a Fermat's number if there are numbers x,y,z ;SPMgt; 0 such that tex2html_wrap_inline279 .).
    4. `there is a run of x consecutive 7's in the decimal expansion of tex2html_wrap_inline283 '.
  3. Suppose that tex2html_wrap_inline285 and tex2html_wrap_inline287 are partially decidable. Prove that ` tex2html_wrap_inline289 ' and ` tex2html_wrap_inline291 ' are partially decidable. Show that ` tex2html_wrap_inline293 ' is not necessarily partially decidable.
  4. Suppose that tex2html_wrap_inline295 is partially decidable. Show that
    1. ` tex2html_wrap_inline297 ' is partially decidable.
    2. ` tex2html_wrap_inline299 ' is partially decidable.
    3. ` tex2html_wrap_inline301 ' is not necessarily partially decidable.
  5. Show that the following predicated are diophontine:
    1. `x is even'
    2. `x divides y'
  6. Technique of reducibilty to show that a predicate is not partially decidable.
    1. Suppose that M(x) is a predicate and k a total computable function such that tex2html_wrap_inline313 iff M(k(x)) does not hold. Prove that M(x) is not partially decidable.
    2. Prove that ` tex2html_wrap_inline319 is total' is not partially decidable.
    3. By considering the function


      show that ` tex2html_wrap_inline319 is total' is not partially decidable. [Hint: use s-m-n theorem and (a)].

  7. Suppose that tex2html_wrap_inline327 is partially decidable and tex2html_wrap_inline329 are computable partial functions. Show that tex2html_wrap_inline331 given by


    is partially decidable. (we take this to mean that tex2html_wrap_inline331 does not hold if any one of tex2html_wrap_inline335 is undefined.)

Subhashis Banerjee
Sat Sep 27 16:37:46 IST 1997