# 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.)

#### Problems:

1. Exercise 3.7 from the textbook.

2. Exercise 3.8 from the textbook.

3. Problem 3.14 from the textbook.

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:
• 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
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.