# The Theory of Computation

## ADDITIONAL EXERCISES FOR CHAPTER 5

• Additional Exercise 1
Give primitive recursive definitions for the following functions:
• the least common multiple of x and y;
• the greatest common divisor of x and y;
• the number of divisors of x and the number of prime divisors of x;
• Euler's function, that is, for a given argument x, the number of positive integers less than x that are relatively prime to x; and
• the index of the leading nonzero bit in the unsigned binary representation of x, where the index is defined as the number of bits following the leading nonzero bit.
• Additional Exercise 2
Classify each of the following sets and its complement as recursive, nonrecursive r.e., or non-r.e.
• The set of all x such that there exists a run of at least x consecutive 7s in the decimal expansion of pi.
• The set of all x such that there exists a run of exactly x consecutive 7s in the decimal expansion of pi.
• The set of all x such that, for every y such that phix(y) converges, there exists a z such that phix(z) converges and phix(z) = 2 phix(y)}.
• The set of all infinite r.e. languages.
• The set of all r.e. languages that are equal to their reverse, i.e., the set of all languages LR={xR | x in L} where L is r.e. and LR=L.
• Additional Exercise 3
Prove or disprove the following statements:
• R.e. sets are closed under exclusive-or (symmetric difference).
• R.e. sets are closed under pointwise sum, i.e., if S and T are two r.e. sets, then the set U = { x | there exists y in S and z in T with x=y+z } is also r.e.
• (harder) Recursive sets are closed under recursive intersection; that is, if S is a recursive set that includes only indices of characteristic functions (i.e., i in S => phii is total and 0/1-valued), then the set { x | for all i in S, phii(x)=1 } is recursive.
• Additional Exercise 4
Prove that every infinite r.e. set has a non-recursive r.e. subset.
• Additional Exercise 5
Prove that every infinite recursive set has a non-r.e. subset.
• Additional Exercise 6
Let f be a total recursive function, A a recursive set, and B an r.e. set. Prove that f-1(A) is recursive and that f(A), f(B), and f-1(B) are r.e.
• Additional Exercise 7
Prove that every r.e. set that obeys the hypotheses of Rice's theorem is creative.

 Back to The Theory of Computation