CSEP 590TU Assignment #1
Autumn 2003

Due: Wednesday, October 8, 2003.

Read chapter 3 of Sipser's text.

Practice Problem: page 147, problem 3.1

Problems:

1. Sipser's text page 147, problem 3.7

2. Sipser's text page 148, problem 3.8

3. Give an implementation-level description of a Turing Machine that on input a string over alphabet {1,2,...,b} produces the next string in lexicographic order. That is, the machine should make one step of an unbounded counter.

4. Describe how to simulate a Turing machine by a '2-stack deterministic pushdown automata' (2-DPDA) which is a machine with a finite state control and two stacks instead of the one tape that a Turing machine has. (The machine can only read the top symbol on each of the two stacks at each step.)

5. Sipser's text page 148, Problem 3.11

6. The definition of a Turing machine was designed to correspond to computation as done by humans but includes an infinite tape which obviously does not exist in the 'real world'. What evidence is there that despite this problem the Turing machine is a more reasonable definition of computation than the definition of a finite state machine?

7. (Bonus) Sipser's text page 149, problem 3.16. HINT: Make a separate argument in the case that the language is finite.