92 Computability Theory Exercises 1. Obviously Tot K. Show that there is no computable set A with Tot A K. Suggestion: Consider the function defined by the equation: f (x) = [[x]](x) + 1 0 if x A if x A. / 2. (a) Assume that f is a total computable one-place nondecreasing function (that is, f (x) f (x + 1) for all x). Further assume that the range of f is infinite. Show that the range of f is a computable set. (b) Suppose that in part (a), we drop the assumption that the range is infinite. Show that the same conclusion still holds. 3. Assume that A is an infinite recursively enumerable set of natural numbers. Show that there is a total computable strictly increasing function g (that is, g(x) < g(x + 1) for all x) whose range is included in A. (It follows from this exercise that every infinite recursively enumerable set has an infinite computable subset.) 4. (a) Show that the intersection of two n-ary recursively enumerable relations is again recursively enumerable. (b) Show that the union of two n-ary recursively enumerable relations is again recursively enumerable. 5. Assume that f is a total computable function. Show that W f (n) n N is recursively enumerable. (That is, a computably indexed union of r.e. sets is r.e.) 6. (a) Show that there is a computable partial function f such that whenever W x = , then f (x) and f (x) W x . (That is, the function f finds some member of W x , provided there is a member.) (b) Assume that R is a recursively enumerable binary relation. Construct a com- putable partial function f such that whenever y R(x, y), then f (x) and R(x, f (x)). (That is, the function f finds some y such that R(x, y), provided there is one.) 7. Show that the set {x | [[x]](x) = 0} (i.e., the set of x's for which [[x]](x) is defined and equals 0) is recursively enumerable but not computable. 8. Let A = {x | [[x]](x) = 0} and B = {x | [[x]](x) = 1}. (a) Show that A and B are disjoint r.e. sets. (b) Show that A and B are computably inseparable, that is, there is no computable set D with A D and B D. Suggestion: Suppose we had such a set D; let d be an index of its characteristic function. What can you say about [[d]](d)? 9. Give an alternative proof of Kleene's theorem as follows. Assume that R is a rela- tion for which both R and R are recursively enumerable. Show that C R , the charac- teristic function of R, has a recursively enumerable graph.