WPI Worcester Polytechnic Institute

Computer Science Department

CS4123 Theory of Computation 
Homework 2 - D 2002


Due Date: Tuesday, April 2nd at 5 pm. 
Help session: Monday, April 1st, 1-2 pm Room: AK219
Late Policy: No late homework will be accepted



  1. (32 points) Show that each of the following functions is primitive recursive.

    For each one of them:

    1. (4 points each) Write down a proof that the function is primitive recursive. That is, show that the function can be computed from the basic functions or previously shown primitive recursive functions (in class or handouts) using composition and primitive recursion definition.

    2. (4 points each) Implement the function using a high level programming language. Your program should satisfy all the following conditions:
      • (i) The only constant used is 0 (zero)
      • (ii) The only functions used are
        • incrementing a value by one (succ)
        • functions that you have previously coded using this set of conditions. For instance, if you need to use the function PLUS defined in class, you need to implement this function, following the definition given in class as part of your code.
      • (iii) It can use composition of functions
      • (iv) It can use recursion (i.e. a function can invoke itself), following a definition by primitive recursion.
      • (v) You cannot use anything not described by the previous items. That is, you CAN ONLY use constants/functions/techniques described in (i) to (iv).
      For instance, if you need to use a constant, say 2, different from 0, then you will express it as succ(succ(0)).

      Turn in a printout of your code and a transcript showing the output produced by your implementation of each function on each of the following inputs: 5, 8, 9, 12.

  2. (10 points) The purpose of this exercise is to show that definition by cases preserves the property of being primitive recursive. More precisely, consider the function f: NxNxN -> N defined by cases as follows:
                   | g(k,m,n),        if p(k,m,n)=1
       f(k,m,n) := |
                   | h(k,m,n),        if p(k,m,n)=0
    where g and h are functions from NxNxN -> N, and p is a function from NxNxN -> {0,1}.

    Prove that if g, h, and p are all primitive recursive functions, then f as defined above is also primitive recursive.

  3. (20 points) (Adapted from Sudkamp, p. 347) Given an arbitrary Turing machine M and input string w, will the computation of M with input w halt in fewer than 100 transitions? Describe a Turing machine that solves this decision problem. In other words, show that the following language L is decidable:
    L = { < M,w > | M halts on input w in fewer than 100 transitions}

  4. (20 points) Exercise 4.10 from textbook (page 169).

  5. (20 points) Exercise 4.12 from textbook (page 169).

Additional Problem for Students taking the course for Graduate Credit

  1. (10 points) Problem 4.13 from textbook (page 169).

Homework Submission