CSE 431 Assignment #1
Spring 2003

Due: Friday, April 11, 2003.

Finish reading chapter 3 of Sipser's text.

Practice Problem: page 147, problem 3.1

Problems:

1. PROBLEM POSTPONED

2. page 148, problem 3.5

3. page 148, Problem 3.8

4. page 148, Problem 3.9 (a)

5. page 149, Problem 3.13

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?