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
{0^{n} 1^{n} | 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 ?