CS 535
                                                       Fall 2010

                      Assignment #6


Date Due: Thursday, December 8 

Reading:  Chapter 3, pages 46-53

Problems :

1. Page 120, #5.12

2. Page 121, #5.16

3. Prove that NSPACE (2  n ) is properly contained in DSPACE (2 
  (n  2 ) ).

4. Prove that {e | M_e accepts the string 00} is c.e.

5.  We have defined a set to be c.e. if it is empty or it is the range of a
total computable function.

Define a set S to be partial c.e. if it is the range of a partial
computable function.

Now since the partial computable functions include the total computable ones,
any c.e. set is a partial c.e. set. 
(Although the empty set is a special case here.)

Prove the converse, that is prove that any partial c.e. set is actually 
a c.e. set.