Homework 1

Department of Computer Science

Worcester Polytechnic Institute

(Bring your homework to my office FL232 before 5 p.m. If I'm not in, please slip your homework under my door.)

- Exercise 3.7 from the textbook.
- Exercise 3.8 from the textbook.
- Problem 3.14 from the textbook.
- 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. - 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. - Consider the function:
g(n) := ``the number of values
*m*such that*m*is prime and*m*<= n''. Examples:- g(4) = 2 since there are two primes less than or equal to 4, namely 2 and 3
- g(1) = 0 since there are no primes less than or equal to 1
- g(13) = 6 since there are six primes less than or equal to 13, namely 2, 3, 5, 7, 11, and 13

**Hint**You can use the "prime" function from the previous problem as a subroutine.

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