# 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:

- Sipser's text page 147, problem 3.7
- Sipser's text page 148, problem 3.8
- 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.
- 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.)
- Sipser's text page 148, Problem 3.11
- 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?
- (Bonus) Sipser's text page 149, problem 3.16. HINT: Make a separate argument in the case that the language is finite.