CS4123 Theory of Computation. A99
Homework 1

Prof. Carolina Ruiz
Department of Computer Science
Worcester Polytechnic Institute

Homework 1

Due on Tuesday, Sept. 7, 1999 at 5 p.m.
(Bring your homework to my office FL232 before 5 p.m. If I'm not in, please slip your homework under my door.)


  1. Exercise 3.7 from the textbook.

  2. Exercise 3.8 from the textbook.

  3. Problem 3.14 from the textbook.

  4. A 2-Head Turing Machine (2HTM) is like an ordinary Turing machine except that it has two heads, head1 and head2, pointing to its tape. Initially, both head1 and head2 are pointing to the leftmost symbol of the input. The transition function is changed to allow for reading, writing, and moving the heads over the tape simultaneously. For example, the transition (q_i,a_1,a_2)->(q_j,b_1,b_2,L,R) specifies that if the machine is currently in state q_i, head1 is reading character a_1, and head2 is reading character a_2, then the machine goes into state q_j, head1 writes symbol b_1 and moves left, and head2 writes symbol b_2 and moves right.
    To avoid conflicts, if both head1 and head2 are both pointing to the same tape cell and both attempt to simultaneously write to this cell, only head1 is allowed to write.
    Prove that every 2-Head Turing Machine is equivalent to an ordinary Turing machine.

  5. Show that the function
                 |  1,   if n is a prime number
      prime(n) = |
                 |  0,   otherwise
    is computable, by writing a C function that computes it. Your C function should receive a non-negative integer as input and should return the right answer in a finite amount of time (i.e. it should terminate). By convention, 0 and 1 are NOT considered prime numbers.

  6. Consider the function: g(n) := ``the number of values m such that m is prime and m <= n''. Examples: Show that the function g is computable, by writing a C function that implements it.
    Hint You can use the "prime" function from the previous problem as a subroutine.

Additional Problems for students taking this course for graduate credit:

  1. Problem 3.9 from the textbook.
  2. Problem 3.16 from the textbook.
  3. Prove that a language L is decidable iff L and its complement CL are both semidecidable. (Note: CL = Sigma* - L)