CS 535
                                                       Fall 2009


                                Assignment #2


Date Due: Tuesday, October 6

Reading: Chapter 5,  pages 90-107

Problems :

1. Prove that any finite language is decidable by a Turing machine,
and that the complement of any finite language is also decidable. 

2. Problem 3.5 on page 50

3. Problem 3.6 on page 50

4.  Explain how you might define a two-headed TM. As usual the TM would have a
single finite tape. 
In particular what would the formal definition look like,
and how could you specify the TM program ?
What would such a TM do in one move if both tape heads were reading 
the same tape square ?

5. Show that any language that a  two headed TM decides, can also be decided by a 1 headed TM. 
To do the explain how you could use our usual single tape and single tape head TM to simulate
the computation of a 2 headed TM as you defined in problem 5.  

6. Let L be a language over a finite alphabet Sigma. 
Show that if L is accepted by some TM then it is accepted by a
TM whose only tape symbols are 0, 1 and B.

7.  Problem 3.16 on page 70