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.)
- 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
- 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''.
Show that the function g is computable, by writing a C function
that implements it.
- 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.
Additional Problems for students taking this course for graduate
- 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)