Next: Numbering computable functions Up: MFCS: Problem set 1 Previous: URM programs

# Substitution, primitive recursion and minimalization

Do the following without writing any programs.

1. Show that for every the following functions are computable:
1. (recall that )
2. mx
2. Suppose that f(x,y) is a computable function and . Show that the function is computable.
3. Suppose that the function g(x) is a total computable function. Show that the predicate is decidable.
4. Show that the following functions are computable:
1. Any polynomial function where
2. LCM(x,y)
3. HCF(x,y)
4. the number of prime divisors of x
5. the number of positive integers less that x which are relatively prime to x. (x and y are relatively prime if HCF(x,y) = 1.)
6. f(0) = 1; f(1) = 2; f(n+2) = f(n) + f(n+1). (f(n) is the Fibonacci number.)
(Hint: show that the function is computable using recursion.)
5. Show that the following are decidable:
1. x is odd
2. x is a power of a prime number
3. x is a perfect cube
6. Suppose that f(x) is a total injective computable function. Prove that is computable.
7. Suppose that p(x) is a polynomial with integer coefficients. Show that the function f(a) = least non-negative integral root of p(x) -a where is computable (f(a) is undefined if there is no such root.)
8. Show that the function

is computable.

Subhashis Banerjee
Fri Sep 5 15:54:45 IST 1997