WPI Worcester Polytechnic Institute

Computer Science Department

CS4123 Theory of Computation 
Homework 2 - B 2002

By Beth Donovan and Carolina Ruiz 

Due Date: Monday, November 11th at 4:30 pm.  
Help session: Friday, November 8, 3-4 pm, FL141



  1. (32 points) [Taken from Kozen, 1997 and Savage, 1998] 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 the first three functions on each of the following {x, y} set of inputs:  {7, 2}; {3, 6}; {5, 5}; {9, 8}.  Use 2, -3, 0, and 1 for the last function.

  2. (8 points) [Taken from Moret, 1998] Verify that the function f defined as follows:

                                    f(0, x) = g(x)
                                    f(i + 1, x) = f(i, h(x))

    is primitive recursive whenever functions g and h are primitive recursive.

  3. (20 points) [Taken from Kozen, 1997] Given an arbitrary Turing machine M, does M have at least 481 states? Describe a Turing machine that solves this decision problem.

  4. (20 points) Consider the following decision problem: Given an arbitrary Turing machine M, is there a word w for which the computation of M with input w halts in fewer than 481 transitions?
    1. Is this problem decidable? Is it semi-decidable?
    2. Explain your answer to Part 1. That is, if you said that the problem is decidable, construct a TM that decides it. If you said that the problem is semi-decidable, construct a TM that semi-decides it. If you said that the problem is not decidable AND not semi-decidable, prove that it is so.

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

Additional Problem for Students taking the course for Graduate Credit

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

Homework Submission