- Solve the problems of Assignment-2 using Rice's theorem.
- Show that the following predicates are partially decidable:
- ` (
*n*fixed). - ` is a perfect square'.
- `
*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 .). - `there is a run of
*x*consecutive 7's in the decimal expansion of '.

- ` (
- Suppose that and are partially decidable. Prove that ` ' and ` ' are partially decidable. Show that ` ' is not necessarily partially decidable.
- Suppose that is partially decidable. Show that
- ` ' is partially decidable.
- ` ' is partially decidable.
- ` ' is not necessarily partially decidable.

- Show that the following predicated are diophontine:
- `
*x*is even' - `
*x*divides*y*'

- `
- Technique of reducibilty to show that a predicate is not
partially decidable.
- Suppose that
*M*(*x*) is a predicate and*k*a total computable function such that iff*M*(*k*(*x*)) does not hold. Prove that*M*(*x*) is not partially decidable. - Prove that ` is total' is not partially decidable.
- By considering the function
show that ` is total' is not partially decidable. [Hint: use s-m-n theorem and (a)].

- Suppose that
- Suppose that is partially decidable and
are computable partial functions. Show that
given by
is partially decidable. (we take this to mean that does not hold if any one of is undefined.)

Sat Sep 27 16:37:46 IST 1997