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. ` (n fixed).
2. ` 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 .).
4. `there is a run of x consecutive 7's in the decimal expansion of '.
3. Suppose that and are partially decidable. Prove that ` ' and ` ' are partially decidable. Show that ` ' is not necessarily partially decidable.
4. Suppose that is partially decidable. Show that
1. ` ' is partially decidable.
2. ` ' is partially decidable.
3. ` ' 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 iff M(k(x)) does not hold. Prove that M(x) is not partially decidable.
2. Prove that ` is total' is not partially decidable.
3. By considering the function

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

7. 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.)

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