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.