next up previous
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 tex2html_wrap_inline143 the following functions are computable:
    1. tex2html_wrap_inline145 (recall that tex2html_wrap_inline147 )
    2. mx
  2. Suppose that f(x,y) is a computable function and tex2html_wrap_inline143 . Show that the function tex2html_wrap_inline155 is computable.
  3. Suppose that the function g(x) is a total computable function. Show that the predicate tex2html_wrap_inline159 is decidable.
  4. Show that the following functions are computable:
    1. Any polynomial function tex2html_wrap_inline161 where tex2html_wrap_inline163
    2. tex2html_wrap_inline165
    3. LCM(x,y)
    4. HCF(x,y)
    5. the number of prime divisors of x
    6. 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.)
    7. f(0) = 1; f(1) = 2; f(n+2) = f(n) + f(n+1). (f(n) is the tex2html_wrap_inline187 Fibonacci number.)
      (Hint: show that the function tex2html_wrap_inline189 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 tex2html_wrap_inline199 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 tex2html_wrap_inline207 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