next up previous
Next: About this document Up: MFCS: Problem set 3 Previous: Decidability and Partial decidability

Recursive and recursively enumerable sets

  1. Let A, B be subsets of tex2html_wrap_inline345 . Define tex2html_wrap_inline347 and tex2html_wrap_inline349 by


    where tex2html_wrap_inline351 defined before. Prove that

    1. tex2html_wrap_inline347 is recursive iff both A and B are recursive.
    2. If tex2html_wrap_inline359 , then tex2html_wrap_inline349 is recursive iff both A and B are recursive.
  2. Let tex2html_wrap_inline367 and let n ;SPMgt; 1. Prove that if B is recursive then the predicate given by tex2html_wrap_inline327 given by


    is decidable.

  3. Let tex2html_wrap_inline375 . Prove that A is recursive iff tex2html_wrap_inline379 is recursive.
  4. For any tex2html_wrap_inline381 , let tex2html_wrap_inline383 . Show that tex2html_wrap_inline385 is r.e for all a. Does the enumeration tex2html_wrap_inline389 include all r.e. sets?
  5. Show that the set tex2html_wrap_inline391 is r.e.
  6. Show that there are total computable functions k,l such that for every x, tex2html_wrap_inline397 and tex2html_wrap_inline399 .
  7. Suppose that A is an r.e set. Show that the sets tex2html_wrap_inline403 and tex2html_wrap_inline405 are both r.e. Show that tex2html_wrap_inline407 is not necessarily r.e. as follows. For ant t let tex2html_wrap_inline411 . Show that for ant t, tex2html_wrap_inline415 is recursive; moreover tex2html_wrap_inline417 and tex2html_wrap_inline419 .
  8. Let f be a unary computable function, and suppose that tex2html_wrap_inline423 , and let tex2html_wrap_inline425 . Prove that g is computable iff A is r.e.
  9. Let f is a unary function. Prove that f is computable iff the set tex2html_wrap_inline435 is r.e.
  10. Let A be an inifinite r.e. set. Show that A can be enumerated without repetitions by a total computable function.
  11. Which of the following sets are recursive? Which are r.e.? Which have r.e. complement?
    1. tex2html_wrap_inline441
    2. tex2html_wrap_inline443
    3. tex2html_wrap_inline445
    4. tex2html_wrap_inline447
    5. tex2html_wrap_inline449 (m is fixed)
    1. Let tex2html_wrap_inline367 and let n ;SPMgt; 1. Prove that id B is r.e then the predicate tex2html_wrap_inline327 given by


      is partially decidable.

    2. Let tex2html_wrap_inline375 . Prove that A is r.e. iff tex2html_wrap_inline379 is r.e..
    3. Prove that tex2html_wrap_inline375 is r.e. iff tex2html_wrap_inline469 or there is a total computable function tex2html_wrap_inline471 such that A = Ran(f). (By a total computable function tex2html_wrap_inline475 from tex2html_wrap_inline345 to tex2html_wrap_inline479 we mean an n-tuple tex2html_wrap_inline483 where each tex2html_wrap_inline485 is a unary computable function and tex2html_wrap_inline487 .)
  12. Suppose that f is a total computable function, A is a recursive set and B is a recursively enumerable set. Show that tex2html_wrap_inline495 is recursive and that f(A), f(B) and tex2html_wrap_inline501 are r.e. but not necessarily recursive. What extra information can be obtained about these sets if f is a bijection?
  13. Use Rice-Shapiro's theorem to show that the following problems are not partially decidable:
    1. ` tex2html_wrap_inline505 '
    2. ` tex2html_wrap_inline507 '
    3. ` tex2html_wrap_inline509 '
    4. ` tex2html_wrap_inline511 '
    5. ` tex2html_wrap_inline513 '
  14. Prove Rice's theorem from the Rice-Shapiro's theorem. [Hint: Suppose that ` tex2html_wrap_inline515 ' is decidable. Then both tex2html_wrap_inline517 and tex2html_wrap_inline519 satisfy the conditions of Rice-Shapiro: consider the cases tex2html_wrap_inline521 and tex2html_wrap_inline523 .].

next up previous
Next: About this document Up: MFCS: Problem set 3 Previous: Decidability and Partial decidability

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