1. (604 students only) Let P(x) = 1 if x > 0 is a multiple of a prime or 0 otherwise. Show P(x) is a p.r predicate.
•
• 2. (604 students only) Let f(t, x) be a p.r function. Let g(i, j, x) be defined as (i) if i ≤ j then it is the sum of f(t, x) for t varying from i through j; (ii) if i > j then g(i, j, x) = 0. Show g(.) is pr.
•
• 3. Let f(x) be the number of primes ≤ x. Show f(x) is p.r.
•
• 4. Let P(x, t) be a computable predicate, Show f(x, y) be the maximum value of t ≤ y such that P(x, t) = 1. If no such t ≤ y exists with P(x, t) = 1, then f(x, y) = 0. Show f(x, y) is p.r.