CS 535
                                                       Fall 2010

                      Assignment #1


Date Due: Tuesday, September 21

Reading:  Chapter 2, pages 36-40, Chapter 4, pages 72-77

Problems :

1. Problem 2.1, part 1 on page 27 - Only use the language 
 {0n 1n | 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 2 on page 27
(For part 2 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

Note: 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. Consider the definition of truth assignment on page 6, and ordered sets on page 10.

For any two propositional formulas F and G, we say  F &le G  if, for any assignment t,
if t(F) = 1 then t(G) =1. 

a. Is this &le relation on propositional formulas transitive ? Why or why not ? 

b. Is it true that for any F and G, either  F &le G  or  G &le F ? Why or why not ?