CS 535
                                                       Fall 2009

                      Assignment #1


Date Due: Tuesday, September 22

Reading:  Chapter 3, pages 47-53 and pages 59-70.

Problems :

1. Problem 2.1, part 1 on page 27 - Only use the language 
 {1n 0n | n>0} instead of the one given in the problem. 

(Note: For this part you should give the full TM specification and program
as is done with parity in example 2.1, page 24. )

2. Problem 2.1, part 3 on page 27
(For part 3 you can just describe how the 1-tape TM would work on an
arbitrary input and not give the full detailed program.)

3. Prove that an infinite language L which is an infinite set of 
natural numbers is decidable if and only if there is a
one-to-one computable function f which enumerates L's elements
in increasing order.
 

4. Problem 2.3,on page 30

This problem concerns a two tape TM, something we haven't discussed yet 
in class, but this is a simple concept and the short discussion of this in the 
textbook should be sufficient. You can also just google "multi-tape Turing
machine" to find other simple examples. 

5. Problem 3.15 on page 70, or more simply stated, 

Show that every infinite decidable set has an undecidable subset.