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.
